ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Помогите решить задачку
18 сообщений из 43, страница 2 из 2
  2  все
Помогите решить задачку
    #36829074
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
Ничего алгоритм Дейкстры не отсекает. Он меняет порядок перебора вершин (в первую очередь на каждом шаге рассматривается наиболее "перспективная", то есть "ближайшая" к исходной для данной итерации, и потому как только ей оказывается целевая вершина, можно сразу утверждать, что найдет кратчайший путь).
"Волна" (breadth-first-search) в принципе расчитана на графы любой топологии (не обязательно прямоугольные сетки), но вершины для перебора хранятся в "обычной" очереди (queue); а в алгоритме Дейкстры всё то же самое, но очередь заменена на кучу (heap) или очередь с приоритетом (priority queue), что суть разные названия одной струтуры данных.
...
Рейтинг: 0 / 0
03.09.2010, 18:48:08
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36829253
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
junior idiotНичего алгоритм Дейкстры не отсекает. Он меняет порядок перебора вершин (в первую очередь на каждом шаге рассматривается наиболее "перспективная", то есть "ближайшая" к исходной для данной итерации, и потому как только ей оказывается целевая вершина, можно сразу утверждать, что найдет кратчайший путь).
"Волна" (breadth-first-search) в принципе расчитана на графы любой топологии (не обязательно прямоугольные сетки), но вершины для перебора хранятся в "обычной" очереди (queue); а в алгоритме Дейкстры всё то же самое, но очередь заменена на кучу (heap) или очередь с приоритетом (priority queue), что суть разные названия одной струтуры данных.

Ну как же не отсекает если отсекает заведомо безперспективные варианты. Он просто туда не переходит.
...
Рейтинг: 0 / 0
03.09.2010, 20:58:25
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36829270
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
rstudioНу как же не отсекает если отсекает заведомо безперспективные варианты. Он просто туда не переходит.
Что значит "не переходит"? Может и перейти, если со временем выяснится, что "перспективные" варианты не дают лучшего результата. Ни одна ситуация не "забывается", а именно это называют "отсечением", когда какое-то подмножество решений вообще исключается из перебора ещё до окончания работы алгоритма, и к нему не возвращаются ни при каких условиях (например, если уже найдено решение, лучшее, чем предельно возможное на этом подмножестве -- простейший алгоритм ветвей и границ). В алгоритме Дейкстры такого не происходит. В частности, если маршрута до целевой вершины не существует вообще, то будут перебраны все вершины графа, достижимые из исходной.
...
Рейтинг: 0 / 0
03.09.2010, 21:25:43
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36829275
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
junior idiotAndreTMА максимумом будет сумма всех клеток, так что это будет задача "пройти по полю из угла в угол, побывав в каждой клетке по одному разу". Алгоритм этот уже известен и реализуется в несколько строк.
Несовсем (не всегда) так.
Случай с чётным количеством строк и чётным количеством столбцов совсем не очевиден.
Вот процедура, заполняющая массив (maxI,maxJ,2) векторами перехода к следующему полю (двигаясь от 1,1 до maxI,maxJ "змейкой", перпендикулярной диагонали), при этом обходятся все поля без пересечений
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
Sub TestSumMaxS()
    i =  1 : j =  1 
    di =  1 : dj = - 1 
    dmove = True
    Do While Not (i = maxI And j = maxJ)
        If dmove And (i =  1  Or j =  1  Or i = maxI Or j = maxJ) Then
            If j =  1  Or j = maxJ Then ni =  1 : nj =  0  Else ni =  0 : nj =  1 
            di = -di: dj = -dj
            dmove = False
        Else
            ni = di: nj = dj
            dmove = True
        End If
        S(i, j,  1 ) = ni: S(i, j,  2 ) = nj
        i = i + ni: j = j + nj
    Loop
End Sub
В вложении - пример работы
...
Рейтинг: 0 / 0
03.09.2010, 21:34:05
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36829297
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
AndreTM
Код: plaintext
1.
2.
3.
4.
    di =  1 : dj = - 1 
...
            ni = di: nj = dj
...
        i = i + ni: j = j + nj

Диагональные перемещения? Скукота.
...
Рейтинг: 0 / 0
03.09.2010, 22:09:47
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36829313
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
junior idiotДиагональные перемещения? Скукота.
Вообще, это было по поводу "Случай с чётным количеством строк и чётным количеством столбцов совсем не очевиден", поскольку для любой матрицы доказывается (как сам метод, так и инвариант алгоритма).

А что, предлагаете стохастически решать? :)
Просто, я "поиск максимума" со слов ТС именно так понял... а про минимум уже рассуждений хватает.
...
Рейтинг: 0 / 0
03.09.2010, 22:27:54
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36829355
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
AndreTMА что, предлагаете стохастически решать?
Нет, предлагаю найти оптимальную "змейку", решив, какую(ие) именно клетку(и) выбросить из полного обхода (который невозможен при чётном количестве столбцов и строк, если не делать диагональных скачков, отсутствие коих, на мой взгляд, подразумевается, поскольку с ними в задаче поиска маршрута минимальной суммы становятся бессмысленными вертикально-горизонтальные перемещения).
...
Рейтинг: 0 / 0
03.09.2010, 23:17:51
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36829360
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Как это полный обход невозможен?
Тут уж все только глубиной стека возвратов будет определяться да мощностями...
...
Рейтинг: 0 / 0
03.09.2010, 23:26:36
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36829370
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
Честно говоря, я не понял что в excel-нике. Два каких-то маршрута, ни один из которых не покрывает всю матрицу.
...
Рейтинг: 0 / 0
03.09.2010, 23:39:11
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36829392
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Ну, это для примера. Рекурсивный поиск минимума и максимума с условием движения только вниз или вправо.
Естественно, можно сделать из этого алгоритма поиск и во все стороны (ну, без диагоналей), но данная реализация будет медленной. Поэтому должно делаться в массиве и с дополнительным массивом-маской пути. Ресурсов, конечно, требует немалых... но и работать будет на любых данных.
...
Рейтинг: 0 / 0
04.09.2010, 00:02:24
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36831837
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
junior idiotНичего алгоритм Дейкстры не отсекает. Он меняет порядок перебора вершин (в первую очередь на каждом шаге рассматривается наиболее "перспективная", то есть "ближайшая" к исходной для данной итерации, и потому как только ей оказывается целевая вершина, можно сразу утверждать, что найдет кратчайший путь).
"Волна" (breadth-first-search) в принципе расчитана на графы любой топологии (не обязательно прямоугольные сетки), но вершины для перебора хранятся в "обычной" очереди (queue); а в алгоритме Дейкстры всё то же самое, но очередь заменена на кучу (heap) или очередь с приоритетом (priority queue), что суть разные названия одной струтуры данных.

гуглим на википедии Дейкстру и читаем


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


Улавливаешь ? Дейкстра доказал что можно найти минимальное расстояние для этой вершины и больше никогда туда не возвращаться. Тоесть отсечь любые дополнительные расчеты "в лоб" с этой вершиной.
...
Рейтинг: 0 / 0
06.09.2010, 14:49:36
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36831967
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
rstudio, я прекрасно знаю, как и почему работает алгоритм Дейкстры.
Но
rstudioОн просто туда не переходит.
rstudioбольше никогда туда не возвращаться.
несколько разные вещи.
Иными словами, ты ни на что не возразил из мною сказанного.
Отсутствие же "дополнительных расчётов" при уже найденном решении (подзадачи) называть "отсечением" -- более чем странно; эдак любое, скажем, аналитическое решение можно записать в "методы отсечения", оно же все варианты в лоб не перебирает.

Классическими примерами алгоритмов с отсечениями являются метод ветвей и границ (и его улучшенная версия -- альфа-бета отсечения) и алгоритм Гомори (который иногда даже так и называют -- "метод отсечений Гомори"). Вот их лучше "погугли в википедии", чтобы называть вещи своими именами.
...
Рейтинг: 0 / 0
06.09.2010, 15:23:33
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36832085
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
junior idiotОтсутствие же "дополнительных расчётов" при уже найденном решении (подзадачи) называть "отсечением" -- более чем странно; эдак любое, скажем, аналитическое решение можно записать в "методы отсечения", оно же все варианты в лоб не перебирает.


В аналитеческое решение к отсечениям можно записать только такое решение, которое отсекает заведомо доказанные провальные ветки . Вот Дейкстра тоже, аналитически доказал, что больше обсчитывать не нужно. Минимальное расстояние есть окончательным и пересчетам не подлежит.
...
Рейтинг: 0 / 0
06.09.2010, 15:59:24
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36832139
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
Ну ладно. Пусть, скажем, поиск корня линейного уравнения a * x = b при a =/= 0, b =/= 0 по аналитической формуле x = b / a тоже будет называться "методом отсечения", раз уж это аналитически доказано и полный перебор не производится.
...
Рейтинг: 0 / 0
06.09.2010, 16:11:25
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36832168
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
junior idiotНу ладно. Пусть, скажем, поиск корня линейного уравнения a * x = b при a =/= 0, b =/= 0 по аналитической формуле x = b / a тоже будет называться "методом отсечения", раз уж это аналитически доказано и полный перебор не производится.

Нет.
Во-первых здесь ограничение потому что на ноль делить нельзя.
Во-вторых, отсечение это по сути сужение расчетов за счето того, что в процессе работы алгоритма были высчитаны некоторые данные, которые по сути доказали несостоятельность дальнейшего развития с этой точки.
...
Рейтинг: 0 / 0
06.09.2010, 16:18:30
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36832255
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
rstudioВо-первых здесь ограничение потому что на ноль делить нельзя.
Никто и не просит:
junior idiota =/= 0, b =/= 0

rstudioВо-вторых, отсечение это по сути сужение расчетов за счето того, что в процессе работы алгоритма были высчитаны некоторые данные, которые по сути доказали несостоятельность дальнейшего развития с этой точки.
Именно так. В процессе работы алгоритма было высчитано отношение b к a, которое по сути доказало несостоятельность дальнейших поисков значений x, удовлетворяющих равенству.
...
Рейтинг: 0 / 0
06.09.2010, 16:38:09
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36832509
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
junior idiot,

ладно, закроем этот разговор. Он уже скорей напоминает разговор о русском языке.
...
Рейтинг: 0 / 0
06.09.2010, 17:39:35
| Ответить | Цитировать | Написать  
Помогите решить задачку
    #36833055
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Ну, в принципе, всё уже понятно.
Минимум ищем по Дейкстре, а максимум - перебором с условием окончания при нахождении первого же полного пути.
Единственный затык - алгоритм поиска максимума при условии того, что у нас чётные M и N более 4, плюс наличие неположительных значений в матрице...
...
Рейтинг: 0 / 0
06.09.2010, 23:47:52
| Ответить | Цитировать | Написать  
18 сообщений из 43, страница 2 из 2
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Помогите решить задачку
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36829074&tid=1343479]:
 0ms
get settings:
 9ms
get forum list:
 9ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 172ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 42ms
get tp. blocked users:
 1ms
others: 202ms
total:  448ms
созд. / загр.: 448ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]