Сап /бНа сегодня надо дописать прогу, как реализовать алгоритм поиска кратчайщего пути в матрице по их значения?3 2 4 51 2 3 34 5 1 1Допустим с точки [1,1]3 до [4,4]1 кратчайщий путь 3->2[2,2]->1[4,3]->1[4,4]. Как написать такой алгоритм на c#? Или другими словами БЫДЛОКОДЕРОВ ТРЕАД с меня как всегда
буамп
>>145239899 (OP)A*
>>145239899 (OP)бамп
анон 300кк/наносекнда вкатываетсяне задавайте ответов
>>145239940молодца
>>145239940/thread
Скоро в шкалку, а дз по инф не сделал?
>>145240000в садик задали дз, хз что делать
>>145240000>0000привет, познакомимся?
>>145240011>11нахуй отсюда
>>145239899 (OP)перебор писать умеешь?
>>145239899 (OP)алгоритм дейкстры/тхреад
>>145240011Это хуйня, я гет ловил пару лет назад
>>145240033так понятно что алгоритм деикстры, как записать то
>>145240024смысле перебор?
>>145239899 (OP)гугли алгоритм прима
>>145240052depth first search, например.
>>145240033Дейкстра подходит для графов в общем виде, для квадратной (да и вообще для декартового пространства) матрицы лучше A*, там волна пытается идти в примерно правильном направлении, и как следствие - работает быстрее.
>>145240079>>145240071>>145240068гугля пока что
>>145240089гуглю*
>>145240093вовремя ты
>>145240120просто я слишком даун и не понимаю, как правилньо матрицу как граф реализовать что бы все это работало
>>145240133ну тебе же связность дана, вот он граф.
>>145240143вот допустим сгенерировал массив рандомный, а что дальше с ним делать? Ибо ничего связаного с графами никогда не писал
>>145240179ничего не делай, гугли работающую прогу.
>>145240179A[i+1] - узел справа от твоего узла, A[i-1] - слева, A[i+sqrt(sizeof(A))] - узел сверху.Но опять же, если у тебя прям матрица, то дейкстру использовать неэффективно, используй астар, сука.
А бочку можно делать в энтом тренде
>>145240229сенкс,гугл мод активейтед
а у меня в оптимизаторе ast выражения вида 0 < x превращались в x < 0 оказывается.
>>145239899 (OP)мм даже бампану. потом попробую спиздить его на решение задачи на степике :)
>>145239899 (OP)привет, их очень много, ты можешь проебатся очень долго с их изучением и т.п. и т.д., данная тема очень и очень серьезная, если у тебя координаты между точками большие (более 200х200, то процессор будет жратьшопиздец).В подавляющем большинстве случаев тебе нужен A*https://www.codeproject.com/articles/15307/a-algorithm-implementation-in-cЛибо: Jump Searchhttps://www.codeproject.com/articles/15307/a-algorithm-implementation-in-c
Это решается динамическим программированием. Строится матрица ответов для частного случая, потом берешь ответ для нужного координата.
>>145240978>>145240987спасибо, уже нашел материал, сейчас изучаю
>>145241066ну сюда кидай, пидор.
>>145241139http://pestantium.blogspot.com/2010/05/blog-post.htmlспиздил отсюда код, перелизал с видео на ютубе что бы оно работало и сейчас пробую переделать под свое задание
>>145241139Начиная с момента FindWave не понимаю как подставить под свое задание, пойду пока покурю, мб идее появяться
>>145241158thx
>>145241216ну ты опиши хоть условия, конкретизируй задачу. че известно? финиш / старт даны? или просто задача пройти по диаганали с де(ин)крементом?
>>145241269Дана матрица произвольного размера, нам нужно от начальной координаты дойти до финальной самым дешевым путем, тойсть нужно по самым дешевым путем из значений в матрице дойти до финальной координатынапример1 2 4 53 8 2 3 1 1 1 26 3 2 1Начиная с [1,1](1) и например идя в [4,4] (1) путь будет такой [1,1] 1 -> [1,2] 2 -> [2,3] 2 ->[3,3] 1 -> [4,4] 1+ + - -- - + -- - + -- - - +
>>145241269>>145241347цена пути получаеться 5
>>145241347> дешёвым.ставь опыты хуле.> муравьиный алгоритм
>>145241375сорри за ё, я просто хохло
>>145239899 (OP)(x2 - x1) / (y2 - y1)Это скажем так коэффициент наклона.0 - идём строго горизонтально (точки на одной линии), Infinity - строго по вертикали.1 - идём шаг вниз, шаг вправо2 - идём два шага вниз, шаг вправо0.5 - шаг вниз, два вправоОтрицат. знач. - всё то же самое, то только вверх и влево.
>>145241386ты наркоман? причём тут Ё?пиздуй на хабр и ищи реализацию поиска муравейника.
>>145241418Не сильно понятно, как это стоит употреблять>>145241424>наркоманХватит бить по больному
Пойду посплю пару часиков, возможно тред еще жив будет и будет тут полезная инфа, а пока что бамп няшей
>>145241468> Не сильно понятно, как это стоит употреблятьникак, это как я нарисовал походу: >>145240804>>145241418 - название алгоритма в студию.>Хватит бить по больномублять, ну как так можно мыслить?
>>145241594тебе тут варианта 4 решения дали, какая тебе еще инфа нужна?
>Вкатился в программирование>Не умеет ни думать, ни гуглить, ни правильно формировать вопросУмри
>>145241805Неа, ты. Не в защиту ОПа конечно, просто все с чего то начинают.
>>145243709> все с чего то начинают.учиться в вузе пора бы блджад.
>>145239899 (OP)короче ОП, скажи че выбрал.либо гони решение которое впиздолисил у однокуров.
>>145239899 (OP)function A*(start, goal, f) % множество уже пройденных вершин var closed := the empty set % множество частных решений var open := make_queue(f) enqueue(open, path(start)) while open is not empty var p := remove_first(open) var x := the last node of p if x in closed continue if x = goal return p add(closed, x) % добавляем смежные вершины foreach y in successors(x) enqueue(open, add_to_path(p, y)) return failure
>>145239899 (OP)волновой метод оптимальный, если у тебя матрица не огромных размеров даже оптимизировать ничего не надо. пускаешь волну от нужной точки и когда координаты целевой точки совпадают с точкой волны строится обратная трасса. пикрил делал себе подобное, правда тут ещё и веса клеток рассчитываются и кружок идёт на строго по центру а по кратчайшему пути
>>145246326
