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

За реализованный алгоритм на Си или Паскале заплачу 10 WMZ (или больше)!! Пишите на [email protected], плз! ОЧЕНЬ НУЖЕН!!!

Клеточный автомат нужен что ли?

Цитата(vax @ 3.4.2004, 01:49)

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

Путь должен быть максимально приближен к прямой или максимально коротким? Это не всегда одно и то же. Для последнего случая хорошо подходит алгоритм волновой трассировки. Вот хорошее описание алгоритма. Вот пример реализации на JavaScript. А вот еще почитать.
А насчет программы, если не найдешь пиши, чойнить наваяем.

Чувствую, меня не правильно понимают.

Что значить максимально приближен к прямой показано на рисунке.


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

Алгоритм поиска кротчайшего пути по карте тут совсем не причем. Да и препятствий нет никаких.

нужно чтобы бы маршрут не отходил далеко от линии, хотя он может быть и не оптимальным так?


Это сообщение отредактировал(а) chipset - 4.4.2004, 08:47

а в каком виде нужно решение?
а то слова "в виде реккурентной функции" не очень понятны
какой у нее аргумент, какой результат?

Добавлю ещё конкретики:

Имеем матрицу 100Х100. Входными данными будут служить координаты центра расхождения x,y (x=50,y=50), углы расхождения a1 и а2 (для начала a1=0, a2=360, т.е. по кругу).

На каждом этапе расхождения от центра в рекурсивной функции вычисляется значение функции, например 1/d (где d расстояние до центра). Это значение и заноситься в матрицу.

Главные критерии алгоритма: чтоб алгоритм расходился по “прямым” и то, что в одну и ту же ячейку не заходила два раза.

Может кто возмется или укажет путь?
Если че непонятно спрашивайте! Очень нужен алгоритм...

А переходы между клетками по диагонали возможны?

можно и по диагонали... это не принципиально... главное чтоб работало!!

Вот примерный вид нужного алгоритма:

/***********************************/

double matr_lev [100][100]; // матрица уровней чего-то вычисляемая как 1/d…
int matr_index[100][100]; // матрица номеров ячейки
int matr_parentindex[100][100]; // матрица номеров родительской ячейки
int curr_index; // здесь храниться номер текущей обсчитываемой ячейки


CalcElement (int x, int y, int parentindex, int ix, int iy, double a, double b,.....)
// x, y - текущие координаты обсчитываемой ячейки
// index - номер ячейки
// ix,iy - координаты центра
// a, b - угол распространения от центра (например, если a=0, b=90, то распространение идет только в первой четверти)
// т. е. возможен вариант когда необходимо расчитать матрицу внутри
какого то угла от центра распространения
... - какие-то твои данные
{
double d=sqrt((pow(x-ix,2)+pow(y-iy,2)); // расстояние до центра
level=1/d; //типа вычесляем уровень чего-то
matr_lev[x,y]= level;
matr_parentindex[x,y]=parentindex; //указываем из какой ячейки
// пришли в текушую, потом сможем востановить маршрут движения.

curr_index++; //увеличиваем счетчик ячеек
matr_index[x,y]=curr_index;

if (level<0.15) exit; //если уровень упал до какого-то значение, то дальше продолжать
//обсчет по этой ветке нет смысла


//дальше идет перебор ближайших ячеек и анализ "куда идти дальше",
//(эту часть алгоритма и требуется написать!!!....) чтоб удовлетворить
// условию "прямых". Когда поняли куда идти вызываем опять же...
CalcElement (xnew, ynew, curr_index, ix, iy, double a, double b, .....)
}

bool razhod (int x, int y, double a1, double a2, double array[100][100])
{
curr_index=1; // обнуляем счетчик ячеек

CalcElement (50, 50, curr_index, 50, 50, 0, 360,.....)
// запускаем рекуррентную функцию…
}

/***********************************/

Как результат работы программы: записать все 3 массива в файлы
текстовые.
По массивам matr_index и matr_parentindex можно будет определить путь от любой точки до центра.


Может кто дописать алгоритм?

гм не очень хорошо понял твой код но придумал небольшой алгоритм:
суть его в том что есть к примеру две клетки одна из них точка старта другая финиш,
с каждым шагом рекурсивной функции , функция берёт и отнимает x старта от x финиша,
проделывает это же самое с y. Далее смотрит какое значение меньше по модулю и если по x значение меньше то идет на шаг назад или вперед зависит от знака с которым получилось вычитание...
вот такое вот придумал, может хоть как то поможет

Цитата(chipset @ 7.4.2004, 05:34)

гм не очень хорошо понял твой код но придумал небольшой алгоритм: суть его в том что есть к примеру две клетки одна из них точка старта другая финиш, с каждым шагом рекурсивной функции , функция берёт и отнимает x старта от x финиша, проделывает это же самое с y. Далее смотрит какое значение меньше по модулю и если по x значение меньше то идет на шаг назад или вперед зависит от знака с которым получилось вычитание... вот такое вот придумал, может хоть как то поможет

Данный алгоритм найдет приблизительно такой путь:

___X
___X
___X
___X
_____X
_______X
_________X

он не будет максимально близок к прямой.

Это сообщение отредактировал(а) LSD - 7.4.2004, 20:59

Посмотрите в поисковике алгоритм Брезенхэма, в частности, алгоритм рисования прямой линии. Это то, что нужно, как я понял из рисунка.
Думаю, что несколько десятков ссылок в яндексе будет.

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

Опиши задачу поподробнее.
Потому как что рисование на экране, что нахождения координат клеток - это одно и тоже.