|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Khovayko [SPAM trap - don't re 2:5020/400 04 Apr 2003 16:07:45
To : anton yakovlev
Subject : Re: Алгоритм реализации "пятнашек" с полем 3x3?
--------------------------------------------------------------------------------
anton yakovlev wrote:
> пронумерованных от 1 до 8. Выдать последовательность перемещений, необходимую
> для перевода "пятнашек" в стандартное состояние. (Под стандартным понимается
> такое состояние ((1,2,3),(4,5,6),(7,8,0)) - по рядам).
>
Решение - поиск в ширину. Гарантирует нахождение наиболее короткого пути
к цели.
Делаешь так:
0. Структура данных.
0.1. Состояние доски с пятнашками. Очевидно, его можно хранить в виде
9-и значного десятичного числа int-a.
0.2. Вводишь функцию "сдвинуть пустышку":
int move_empty(int cur_board, int direction);
Hа входе она берет текущее состояние доски и направление, на выходе
возвращает новое состояние доски. Реализуется такая функция через
вспомагательный массив перестановок 9x4x2.
Если движение пустышкив данном направлении невозможно, функция
возвращает ноль.
0.3. Вводишь map <int, int> M; где хранишь пары: тек.
состояние -> пред. состояние.
0.4. Вводишь очередь обхода queue<int> Q.
Алгоритм:
1. Инициализация:
1.1. M[0] = 0; M[начальное состояние] = 0; Положили в map заглушки.
1.2. Q.push_back(начальное состояние); Положили в очередь начальное
состояние.
2. Поехали!
while(Q.empty()) {
int cur_board = Q.front(); // Выташили очередное сотояние из очереди
q.pop(); // Может, ошибаюсь с именем метода.
Hужно просто удалить вытащеный ранее
элемент из головы очереди.
if(cur_board == 12345678890) { // Если дошли до цели -
do { // Печатаем найденый путь перестановок
PRINT cur_board;
cur_board = M[cur_board];
} while(cur_board);
exit(); // И выходим
}
// Цель еще не достигнута
// Пытаемся пойти по всем направлениям
for(int dir_move = 0; dir_move < 4; dir_move++) {
int next_board = move_empty(cur_board, dir_move);
if(M.count(next_board) == 0) { // Если в таком новом состоянии еще
не были:
M[next_board] = cur_board; // Запомним его и его предка
Q.push_back(cur_board); // и положим в очередь на анализ
} // if M
} // for dir
} // while Q
PRINT "Hет решения";
--
#include <best/regards>
Oleg Khovayko http://olegh.spedia.net
PS/ATTN: Reply to reverted address net.comcast@olegh
--- ifmail v.2.15dev5
* Origin: http://www.ftc.gov/opa/2001/04/spam.htm (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
