поиск пути для кубика, в матрице nxn Опции

[Тёмный Эльф]

Программа, откомпилированная на Microsoft Visual Studio. NET (без оптимизации) вычислила путь для n = 10 за ВНИМАНИЕ 1450 секунды
(Процессор Intel Pentium 4 CPU 2.80GHz)

Сообщение отредактировано: Тёмный Эльф - 27.11.2007 2:44

[hardcase]

Программа, откомпилированная на Microsoft Visual Studio. NET (без оптимизации) вычислила путь для n = 10 за ВНИМАНИЕ 1450 секунды
(Процессор Intel Pentium 4 CPU 2.80GHz)

Это какая такая программа??

[Тёмный Эльф]

Это какая такая программа??

Это программа xds. В прикрепленных файлах она.
Но вообще странно, теперь я откомпилировала ее с оптимизацией по скорости, а результат получился хуже (на 100 секунд больше). Возможно, это потому, что у меня много программ работало одновременно?

Сообщение отредактировано: Тёмный Эльф - 27.11.2007 3:36

[xds]

Вот мой оригинальный вариант (BP 7.0), только добавлено измерение времени:
 CUBE.PAS ( 1.48 килобайт ) Кол-во скачиваний: 782

[spill]

Есть поиск в ширину:
1. Первую клетку пометить числом 1.
2. Поместить в очередь координаты первой клетки
3. Пока очередь не пуста нелать:
3.1. Извлечь из очереди координаты очередной клетки
3.2. Всех непомеченных и соседей (с учетом границ и "темной" грани) этой клетки пометить числом, на 1 большим, чем число, которым помечена эта клетка.
3.3. Добавить в очередь координаты этих соседних клеток.

По окончании работы нужно построить оптимальный путь. Первой будет финишная клетка. Второй - соседняя с ней клетка, помеченная наименьшим числом. Третья - наименьшая из соседей второй ит.д.