Проблемы с движением гальки
-
Основы задачи о движении гальки
- Задача о движении гальки связана с перемещением объектов на графах с ограничениями на количество объектов в вершинах.
- Применяется в планировании движения роботов и сетевой маршрутизации.
- Известна головоломка «15» как пример задачи о движении гальки.
-
Формулировка задачи
- Граф G с n вершинами и набором галек P из k < n.
- Отображение S: P → V, где S(i) ≠ S(j) для i ≠ j.
- Один шаг m = (p, u, v) включает передачу гальки p из u в v.
- Задача состоит в поиске последовательности ходов, преобразующей S0 в S+.
-
Вариации задачи
- Ограничение структуры графа: дерево, квадратная сетка, двусвязный граф.
- Случай с взаимозаменяемыми или немаркированными камешками.
- Поиск не только достижимости, но и оптимальной последовательности ходов.
-
Сложность задачи
- Задача с помеченными гальками NP-сложна и APX-сложна.
- Задача без маркировки может быть решена за полиномиальное время с определенной метрикой стоимости, но NP-сложна для других метрик.
Полный текст статьи: