Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Помогите решить задачку / 25 сообщений из 43, страница 1 из 2
  1  все
30.08.2010, 17:08:22
    #36819615
dimbasbear
dimbasbear
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
Дана матрица (размерность может быть любая) заполненная числами.

Код: plaintext
1.
2.
3.
4.
5.
   A     B     C     D     E 
 1 )  4       5       3       6       7 
 2 )  6       10     11      15       0  
 3 )  5       3       6       7       8 
 4 )  5       1       3       6       7
При переходе из одной ячейки в другую - числа этих ячеек суммируются. Как дойти из ячейки A1 в E4 чтобы сумма была минимальной и наоборот ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.08.2010, 18:23:07
    #36819786
OZKA
OZKA
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
dimbasbearПри переходе из одной ячейки в другую - числа этих ячеек суммируются. Как дойти из ячейки A1 в E4 чтобы сумма была минимальной и наоборот ?

В лоб: перебором всех путей и суммой получающейся в процессе каждого пути. Университетов не заканчивали, так что о возможном математическом методе можем и не знать...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.08.2010, 20:01:48
    #36819921
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
Алгоритм Дейкстры или Priority-First-Search (что то же самое).
Далее -- google/wikipedia, что больше нравится.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.08.2010, 00:50:44
    #36820164
Ренат
Ренат
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
dimbasbear,

строишь рекурсивную функцию, каторая проверяет путь через все соседние клетки самой себя. И возращаешь пару: путь и сумма.
зы. это без математики, самый банальное 20 строчное решение.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.08.2010, 10:18:47
    #36820452
dimbasbear
dimbasbear
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
не могли бы вы привести конкретный пример на любом из языков, например pascal
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.08.2010, 11:11:33
    #36820565
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
Конечно .
Пожалуйста.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.08.2010, 14:33:09
    #36821289
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
Еще бы уточнить - путь строится любом направлении, или только вправо/вниз/(вправо-вниз)?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.08.2010, 15:33:26
    #36821489
dimbasbear
dimbasbear
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
AndreTMЕще бы уточнить - путь строится любом направлении, или только вправо/вниз/(вправо-вниз)?

Строиться может в любом направлении важно чтобы когда добрался до конечной точки сумма была максимальной или минимальной :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.08.2010, 17:01:48
    #36821771
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
Похоже мы имеем дело с графом, у которого "веса" стоят на вершинах. Для Дейкстры надо будет сделать перерасчёт.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.08.2010, 17:51:58
    #36821958
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
maytonПохоже мы имеем дело с графом, у которого "веса" стоят на вершинах. Для Дейкстры надо будет сделать перерасчёт.
Он же тривиален и делается "на лету".
Хотя может быть сделан, кстати, двумя разными способами (считать весом дуги вес вершины, для которой она является исходящей или для которой она является входящей), которые будут давать один и тот же результат (маршрут).

Что-то в этом роде на питоне:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
import heapq

data = [[ 4 ,   5 ,   3 ,   6 ,   7 ],
        [ 6 ,  10 ,  11 ,  15 ,   0 ],
        [ 5 ,   3 ,   6 ,   7 ,   8 ],
        [ 5 ,   1 ,   3 ,   6 ,   7 ]]

H = len(data)
W = len(data[ 0 ])
v = set()
pq = []
heapq.heappush(pq, ( 0 , ( 0 ,  0 ), []))
while pq:
    l, c, p = heapq.heappop(pq)
    if c == (W -  1 , H -  1 ):
        break
    v.add(c)
    for dy in xrange(- 1 ,  2 ):
        for dx in xrange(- 1 ,  2 ):
            x, y = c[ 0 ] + dx, c[ 1 ] + dy
            if x <  0  or y <  0  or x >= W or y >= H or dx * dy !=  0 :
                continue
            if (x, y) in v:
                continue
            heapq.heappush(pq, (l + data[y][x], (x, y), p + [c]))

p.append(c)
print "Best path: %s" % " -> ".join(map(str, p))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.08.2010, 19:54:27
    #36822224
Унрегистеред
Унрегистеред
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
Это, блин, азбука (см.). С гарантией делается ТОЛЬКО прямым перебором. Любая эвристика дает только наиболее вероятный путь.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.08.2010, 20:00:45
    #36822238
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
УнрегистередЭто, блин, азбука (см.). С гарантией делается ТОЛЬКО прямым перебором. Любая эвристика дает только наиболее вероятный путь.
Чушь сказал. Ты хоть понял что мы говорим об Алгоритме Дейкстры? Какие прямые переборы?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.09.2010, 12:59:24
    #36823455
Унрегистеред
Унрегистеред
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
Прошу прощения. Невнимательно прочел исходный пост, показалось, что речь идет о максимальной сумме.
Для минимальной суммы (если значения неотрицательны) действительно будет работать алгоритм Дейкстры. И вообще любой рекурсивный алгоритм, выбирающий соседний элемент с меньшим весом.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.09.2010, 13:12:05
    #36823493
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
Унрегистеред,
Любая задача максимизации однозначной функции может быть переформулирована в задачу минимизации другой однозначной функции; решения этих задач (точки оптимума) будут совпадать. Это же очевидно.
"F(x) -> max" эквивалентно "G(x) = -F(x) -> min"
В данной задаче достаточно приписать минус ко всем числам в матрице. Или переопределить оператор сравнения элементов priority queue (для c++/c#/java).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.09.2010, 13:25:46
    #36823549
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
junior idiot
Код: plaintext
1.
2.
3.
data = [[ 4 ,   5 ,   3 ,   6 ,   7 ],
        [ 6 ,  10 ,  11 ,  15 ,   0 ],
        [ 5 ,   3 ,   6 ,   7 ,   8 ],
        [ 5 ,   1 ,   3 ,   6 ,   7 ]]

Я тут прикинул на глаз. Оптимальный путь должен быть (для 4-х связных соседей) примерно такой:

Код: plaintext
1.
2.
3.
data = [[ 4                  ],
        [ 6 ,                ],
        [ 5 ,   3              ],
        [     1 ,   3 ,   6 ,   7 ]]

Стоимость = 35.

У тебя такой-же ответ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.09.2010, 13:33:02
    #36823575
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
Похоже, что да.
Код: plaintext
Best path: ( 0 ,  0 ) -> ( 0 ,  1 ) -> ( 0 ,  2 ) -> ( 1 ,  2 ) -> ( 1 ,  3 ) -> ( 2 ,  3 ) -> ( 3 ,  3 ) -> ( 4 ,  3 )
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.09.2010, 13:37:11
    #36823588
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
А максимум, после добавления строки
Код: plaintext
data = [[-x for x in r] for r in data]
получается вот таким маршрутом:
Код: plaintext
Best path: ( 0 ,  0 ) -> ( 0 ,  1 ) -> ( 1 ,  1 ) -> ( 2 ,  1 ) -> ( 3 ,  1 ) -> ( 3 ,  2 ) -> ( 4 ,  2 ) -> ( 4 ,  3 )
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.09.2010, 13:42:44
    #36823611
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
junior idiotА максимум, после добавления строки
Код: plaintext
data = [[-x for x in r] for r in data]
получается вот таким маршрутом:
Код: plaintext
Best path: ( 0 ,  0 ) -> ( 0 ,  1 ) -> ( 1 ,  1 ) -> ( 2 ,  1 ) -> ( 3 ,  1 ) -> ( 3 ,  2 ) -> ( 4 ,  2 ) -> ( 4 ,  3 )

Хотя это весьма глупо.
Также как и это:
junior idiot
Унрегистеред,
Любая задача максимизации однозначной функции может быть переформулирована в задачу минимизации другой однозначной функции; решения этих задач (точки оптимума) будут совпадать. Это же очевидно.
"F(x) -> max" эквивалентно "G(x) = -F(x) -> min"
В данной задаче достаточно приписать минус ко всем числам в матрице. Или переопределить оператор сравнения элементов priority queue (для c++/c#/java).
Ляпнул неподумавши.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.09.2010, 14:44:31
    #36823835
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
junior idiotПохоже, что да.
Код: plaintext
Best path: ( 0 ,  0 ) -> ( 0 ,  1 ) -> ( 0 ,  2 ) -> ( 1 ,  2 ) -> ( 1 ,  3 ) -> ( 2 ,  3 ) -> ( 3 ,  3 ) -> ( 4 ,  3 )

Если слегка изменить исходные данные. Ввести туда скажем бесконечно большой вес (для простоты пускай будет X), то постановка приобретает несколько иной оттенок.
Код: plaintext
1.
2.
3.
4.
5.
   A     B     C     D     E 
 1 )  1       1       1       1       1 
 2 )  1      X     X     X      1  
 3 )  1       1      X      1       1 
 4 )  1       1      X      1       1
Это похоже на лабиринт. И декартовый порядок вершин и наличие непроходимых рёбер, наталкивают на мысль о волне .
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.09.2010, 14:52:13
    #36823863
rstudio
rstudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
а там отсечения есть ?
например если на промежуточном этапе получили сумму которая больше чем сумма какого нибудь варианта до этого, то закончить поиск и перейти к следующему.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.09.2010, 15:06:23
    #36823922
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
У "волны" нет отсечений. Вернее для неё отсечения безсмысленны т.к. на каждом уровне рекурсии происходит проверка следующего уровня и тут-же возврат наверк для перехода к следующей ветке. Да и сама рекурсия там "вырождена" в вычисления на декартовой плоскости.

Для Дейкстры - не знаю. Надо подумать.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 14:54:08
    #36828359
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
Вообще, ТС сказал, что двигаться можно в любом направлении (я так понимаю, что и по диагонали, и влево, и вверх... естественно, без пересечений пути).
Тогда задача нахождения минимального пути решается по Дейкстре (ну, граф будет немного побольше, но это непринципиально).
А максимумом будет сумма всех клеток, так что это будет задача "пройти по полю из угла в угол, побывав в каждой клетке по одному разу". Алгоритм этот уже известен и реализуется в несколько строк.

Если же матрица будет содержать и отрицательные значения, то минимум можно найти по Беллману-Форду, а максимум можно посчитать и перебором путей, например...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 15:31:13
    #36828507
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
AndreTMВообще, ТС сказал, что двигаться можно в любом направлении (я так понимаю, что и по диагонали, и влево, и вверх... естественно, без пересечений пути).
Думаю нет.

Тогда задача нахождения минимального пути решается по Дейкстре (ну, граф будет немного побольше, но это непринципиально).
Волна - это тот-же Дейкстра. Только частный случай, оптимизированный для декартова порядка вершин и одинаковых весов дуг.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 15:46:10
    #36828566
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
AndreTMА максимумом будет сумма всех клеток, так что это будет задача "пройти по полю из угла в угол, побывав в каждой клетке по одному разу". Алгоритм этот уже известен и реализуется в несколько строк.
Несовсем (не всегда) так.
Случай с чётным количеством строк и чётным количеством столбцов совсем не очевиден.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2010, 18:19:27
    #36829010
rstudio
rstudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачку
Да, Дейкстра похоже тот же обход с отсечениями
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Помогите решить задачку / 25 сообщений из 43, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 635ms
Закрыть
start [/forum/moderation_log.php?user_name=%D0%B5%D0%B6%D0%B8%D0%BA]:
 0ms
get settings:
 9ms
get forum list:
 10ms
get settings:
 6ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 60ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 52ms
get tp. blocked users:
 1ms
others: 464ms
total:  635ms
x
x
Закрыть


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