Help! Алгоритм обхода конем

   Пиплы, нужен алгоритм для обхода конем поля M*N с началом в точке x1,y1 и концом:) в x2,y2. Наверняка многие решали эту или подобную задачу, наверняка многие даже ее решили. Я тоже думал, что решил.
   Стандартный алгоритм (рекурсивный) работает ОООЧЕНЬ(!) долго,
а при ходе на поле, с которого наименьшее кол-во ходов, х... знает где окажешься в конце. Так вот, вдруг найдется такой умный человек, знающий быстрый, и главное работающий алгоритм, пусть поделится! please!!!
   Жду ответа...
   С уважением, ShtacketT    

Сообщение отредактировано: GrAnd - 22.04.03, 11:38

Посмотри на http://www.softcraft.ru/
там была статья на эту тему, по-моему в разделе по автоматному программированию

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

трудоемкость поиска самым примитивным алгоритмом - n²*m².

Как-то я писал прогу на Си. Держи, может поможет
Компилить под дос
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

unsigned int **board;
int BRD_SIZE;
int X0, Y0;
int shift_x[8], shift_y[8];
int NSQ;
unsigned long cnt_rec;

void Try(int move_num, unsigned int x, unsigned int y, int *result)
{
     int k;
     int u,v;
     int res;

     k = 0;
     u = 0;
     v = 0;
     res = 0;

     cnt_rec++;
     for (k = 0; k < 8 || res != 0; k++)
     {
           res = 0;
           u = x + shift_x[k];
           v = y + shift_y[k];
           if (u >= 0 && u < BRD_SIZE && v >= 0 && v < BRD_SIZE)
                 if (board[u][v] == 0)
                 {
                       board[u][v] = move_num;
                       if (move_num < NSQ)
                       {
                             Try(move_num + 1, u, v, &res);
                             if (!res)
                                   board[u][v] = 0;
                       } else res = 1;
                 }

           gotoxy(1, 1);
           printf("cnt: \%ld move: \%d\n", cnt_rec, move_num);
           for (int i = 0; i < BRD_SIZE;i++)
           {
                 for(int j = 0; j < BRD_SIZE; j++)
                       printf("\%2d ", board[i][j]);
                 printf("\n");
           }
     }
     *result = res;
}

void main(int argc, char **argv)
{
     if(argc < 4)
     {
           printf("USE: \n\thorse <BOARD_SIZE> <START_X> <START_Y>\n");
           return;
     }
     BRD_SIZE = atoi(argv[1]);
     X0 = atoi(argv[2]);
     Y0 = atoi(argv[3]);
     if (X0 > BRD_SIZE || Y0 > BRD_SIZE)
           return;

     board = (unsigned int**)malloc(sizeof(unsigned int*)*BRD_SIZE);
     for (int i = 0; i < BRD_SIZE; i++)
           board[i] = (unsigned int*)malloc(sizeof(unsigned int)*BRD_SIZE);

     int res_fin;
     clrscr();
     printf("Ќ з­Ґ¬ вга Є®­п: \n");
     cnt_rec = 0;
     NSQ = BRD_SIZE*BRD_SIZE;

     shift_x[0] = -2; shift_y[0] =  1;
     shift_x[1] = -1; shift_y[1] =  2;
     shift_x[2] =  1; shift_y[2] =  2;
     shift_x[3] =  2; shift_y[3] =  1;
     shift_x[4] =  2; shift_y[4] = -1;
     shift_x[5] =  1; shift_y[5] = -2;
     shift_x[6] = -1; shift_y[6] = -2;
     shift_x[7] = -2; shift_y[7] = -1;

     for (i = 0; i < BRD_SIZE; i++)
           for (int j = 0; j < BRD_SIZE; j++)
                 board[i][j] = 0;

     board[X0-1][Y0-1] = 1;
     Try(2, X0-1, Y0-1,&res_fin);
     if (res_fin)
     {
           printf("ђҐиҐ­ЁҐ: \n");
           for (i = 0; i < BRD_SIZE; i++)
           {
                 for (int j = 0; j < BRD_SIZE; j++)
                       printf("\%2d ", board[i][j]);
                 printf("\n");
           }
     } else printf("ђҐиҐ­Ёп ­Ґв.\n");
     for (i = 0; i < BRD_SIZE; i++)
           free(board[i]);
     free(board);
}

  spaun , за прогу спасибо  ;)

  shadeofgray , а немного поподробнее можно? Что-то из меня граффер, как из ...
вообщем, из того, что нашел про поиск пути в графе я не очень-то уяснил, причем тут какие-то дуги, векторы и т.д.. Ну, не все здесь хорошие математики

Цитата

вообщем, из того, что нашел про поиск пути в графе я не очень-то уяснил, причем тут какие-то дуги, векторы и т.д..

При самом прямом том:)

Начну с начала. Граф - это набор вершин, некоторые из которых соединены друг с другом. То, чем соединяют, называют по-разному: ребра, дуги, отрезки... Двигаясь по этим самым ребрам можно переходить из одной вершины в другую. В некоторых задачах каждому ребру соответствует длина (ещё называется весом).
Задачи поиска кратчайшего пути на графе делятся на два типа:
на поиск пути из минимального числа ребер,
и на поиск пути с минимальной суммой длин ребер.

Идея вот в чем - задачу обхода конем можно свести к задаче поиска кратчайшего пути из одной точки графа в другую. Пусть каждой клетке поля соответствует вершина графа. Пусть каждую пару клеток, которые разделяет один ход коня, соединяет ребро. Тогда можно использовать один из большого числа алгоритмов для поиска кратчайшего пути из одной вершины в другую (или доказательства отсутствия пути вообще).

   Х-мм, спасибо. Нужно обдумать.  А ты (shadeofgray)  говоришь,  что длина ребер в каждой задаче меняется.  Здесь длина не меняется?
Правильно ли я понимаю, что задача решается так :
   Создается граф из M*N вершин,  где каждая вершина означает клетку и соеденина с теми вершинами-клетками, на которые он может походить.
Далее юзая какой-то алгоритм, находим путь из вершины x1,y1 в вершину
x2,y2 (или один из них - т.к. если их несколько, то их длина одинакова)
    p.s. spaun , ммм, это же рекурсия?!  Но все равно спасибо

Цитата shadeofgray, 22.04.03, 21:30:11

задачу обхода конем можно свести к задаче поиска кратчайшего пути из одной точки графа в другую.

ну не скажи. вопервых надо обходить все клетки, тогда как кратчайший путь - ето явно путь, затрагивающий не все клетки. если ето учитывать, то представление поля в виде матрицы смежности ничем не лучше простого задания правил перехода.

у меня дома есь программа на паскале, я её написал в своё время, не подозревая об евристическом правиле какогото мужика. на самом деле ето правило годится лишь для поиска одного пути, а моя программа ищет сразу все (последовательно ;D) и даже может записывать их на диск. есть даже кое-какая оптимизация. она выдаёт результат для матриц 5*5....13*13, 15*15 и почемуто 23*23, тогда как неоптимизированная программа не выдаёт уже 7*7. для 6*6 таких путей помнится ~240 000, а для 7*7 у меня уже не хватает терпения (оно кончается на нескольких десятках миллиардов).

Сообщение отредактировано: wormball - 24.04.03, 14:19

   Хмм, wormball, а может ты еще и алгоритм помнишь? Или хотя бы прога с русскими (то бишь с понятными) комментариями? Было бы неплохо поиметь (если, конечно, не жаль и нет копирайта). Кстати, что у тебя с "э"? Просто слово "евристическое" навевает мысли об антисемизме Без обид.

прога у меня без комментариев, к тому же дома. алгоритм помню, но с трудом. с "э" у меня всё в порядке, просто у меня субъективное ощущение, что так красивее звучит.

алгоритм приблизительно таков: для каждой клетки вычисляется, во сколько клеток из неё возможен ход, соответственно ежели получается, что при ходе возникают клетки, из которых невозможен выход, то такой ход не производится. для этого даже существует специальный массив: в начале он состоит полностью из нулей, а по мере хождения клетки, смежные (достижимые за 1 ход) с клеткой, куда походили, получают приращение на 1. соответственно если какая-то клетка достигла значения 8, то мы идём по неправильному пути.

помнится это не единственная оптимизация, только я щас не помню

Цитата ShtacketT, 24.04.03, 15:01:40

Здесь длина не меняется?
Правильно ли я понимаю, что задача решается так :

да, всё верно. Длина ребер постоянная, задача решается именно так.

Цитата ShtacketT, 24.04.03, 15:01:40

p.s. spaun , ммм, это же рекурсия?!  Но все равно спасибо

отвечу за spaun`a: это простейший алгоритм поиска кратчайшего пути, т.н. волновой алгоритм.
может реализоваться как рекурсивно, так и нерекурсивно. Вопрос лишь в оформлении.