Форум программистов, компьютерный форум, киберфорум
Наши страницы
Haskell
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
dgimazetdinov
0 / 0 / 0
Регистрация: 20.03.2018
Сообщений: 7
1

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

30.04.2019, 11:18. Просмотров 520. Ответов 9
Метки нет (Все метки)

Всем доброго времени суток!
помогите пожалуйста реализовать код на Haskell "программа, способная отвечать на запросы и возвращать кратчайший путь до заданной вершины (в случае отсутствия последней - сообщять об ошибке)"

заранее всем спасибо!
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.04.2019, 11:18
Ответы с готовыми решениями:

Найти кратчайший путь из вершины u в вершину v
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем сможет :sorry:...

Алгоритм Дейкстры - Найти кратчайший путь от 1 вершины
Вот рисунок по которому нада найти кратчайший путь от 1 вершины помагите плизз

Определить кратчайший путь от начальной вершины к конечной
определить кратчайший путь от начальной вершины к конечной. заполнить ленточную матрицу шириной 3,...

Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины
Здравствуйте! Помогите пожалуйста решить задачу. Найти все вершины неориентированного графа, к...

Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины
Здравствуйте.Помогите пожалуйста решить задачу. Найти все вершины неориентированного графа, к...

9
Catstail
Модератор
24608 / 12515 / 2285
Регистрация: 12.02.2012
Сообщений: 20,334
30.04.2019, 11:26 2
Эта формулировка неконкретна. Задача на графы? Как задается граф? Каков его тип? Что за запросы? Только не надо писать: "так в методичке"!
0
dgimazetdinov
0 / 0 / 0
Регистрация: 20.03.2018
Сообщений: 7
30.04.2019, 11:33  [ТС] 3
да, задача на графы.
граф задаётся перечислением вершин.g=[[1,2],[0,2,3],[0,1,3,4],[1,2,4,5],[2,3,5],[3,4]]
под запросом понимается нахождение кратчайшего пути от одной вершины до другой.
0
Catstail
Модератор
24608 / 12515 / 2285
Регистрация: 12.02.2012
Сообщений: 20,334
30.04.2019, 11:44 4
Обход в ширину:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
mark :: [Int] -> Int -> [Int]
mark chk n | (n == 0) = 1 : (tail chk)
           | otherwise = (head chk) : (mark (tail chk) (n-1))
 
putInQue :: [(Int,[Int])] -> Int -> [Int] -> [Int] -> [Int]
putInQue g n chk que = que ++ (filter (\ x -> (chk !! x) == 0) (snd (g !! n)))
 
isBound ::  [(Int,[Int])] -> Int -> Int -> Bool
isBound g n m = m `elem` (snd (g !! n))
 
bfs' g fin que chk pth | ((length pth) > 0) && (isBound g (last pth) fin) = pth ++ [fin]
                       | (putInQue g hq chk tq) == tq = (bfs' g fin tq chk (init pth))
                       | otherwise = (bfs' g fin (putInQue g hq chk tq) (mark chk hq) (pth ++ [hq])) where tq=(tail que); hq=(head que);
                       
bfs g start fin = bfs' g fin [start] (take (length g) $ repeat 0) []
Проверка:

Haskell
1
2
3
4
5
6
Main> bfs [(0,[1,2]),(1,[0,2,3]),(2,[0,1,3,4]),(3,[1,2,4,5]),(4,[2,3,5]),(5,[3,4
])] 1 5
[1,0,2,3,5]
Main> bfs [(0,[1,2]),(1,[0,2,3]),(2,[0,1,3,4]),(3,[1,2,4,5]),(4,[2,3,5]),(5,[3,4
])] 2 4
[2,4]
Граф у меня задается немного не так, как в задании. Позже подгоню.
1
30.04.2019, 11:44
dgimazetdinov
0 / 0 / 0
Регистрация: 20.03.2018
Сообщений: 7
30.04.2019, 11:58  [ТС] 5
Очень благодарен! буду разбирать что к чему
0
Curry
2952 / 2024 / 252
Регистрация: 01.06.2013
Сообщений: 4,420
Записей в блоге: 8
30.04.2019, 18:44 6
Я так понял, что
Цитата Сообщение от dgimazetdinov Посмотреть сообщение
[[1,2],[0,2,3],[0,1,3,4],[1,2,4,5],[2,3,5],[3,4]]
k-ый элемент списка задаёт номера вершин соединяющихся с k-ой точкой. Тогда
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
import Data.List
import Data.Function
 
job :: Int -> Int -> [[Int]] -> [Int]
job from to gr = reverse $ go [from] from
    where go p fr 
            | fr == to  = p
            | otherwise = case filter isFound $ map (\x -> go (x:p) x) $ 
                                     filter (`notElem` p) (gr !! fr) of
                            [] -> []
                            l  -> minimumBy (compare `on` length) l
          isFound (x:_) = x == to
          isFound _ = False
1
Catstail
Модератор
24608 / 12515 / 2285
Регистрация: 12.02.2012
Сообщений: 20,334
01.05.2019, 10:15 7
Подогнал под условия задачи:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
mark :: [Int] -> Int -> [Int]
mark chk n | (n == 0) = 1 : (tail chk)
           | otherwise = (head chk) : (mark (tail chk) (n-1))
 
putInQue :: [(Int,[Int])] -> Int -> [Int] -> [Int] -> [Int]
putInQue g n chk que = que ++ (filter (\ x -> (chk !! x) == 0) (snd (g !! n)))
 
isBound ::  [(Int,[Int])] -> Int -> Int -> Bool
isBound g n m = m `elem` (snd (g !! n))
 
bfs' g fin que chk pth | ((length pth) > 0) && (isBound g (last pth) fin) = pth ++ [fin]
                       | (putInQue g hq chk tq) == tq = (bfs' g fin tq chk (init pth))
                       | otherwise = (bfs' g fin (putInQue g hq chk tq) (mark chk hq) (pth ++ [hq])) 
                         where tq=(tail que); hq=(head que);
                       
bfs g start fin = if (start >= lg) || (start < 0) || (fin >= lg) || (fin < 0) then 
                      error "Bad number of vertex!"
                  else 
                      bfs' (zip [0..] g) fin [start] (take lg $ repeat 0) []
                  where lg=length g
Проверка:

Haskell
1
2
3
4
5
6
*Main> bfs [[1,2],[0,2,3],[0,1,3,4],[1,2,4,5],[2,3,5],[3,4]] 1 5
[1,0,2,3,5]
*Main> bfs [[1,2],[0,2,3],[0,1,3,4],[1,2,4,5],[2,3,5],[3,4]] 2 4
[2,4]
*Main> bfs [[1,2],[0,2,3],[0,1,3,4],[1,2,4,5],[2,3,5],[3,4]] 2 12
*** Exception: Bad number of vertex!
0
Curry
2952 / 2024 / 252
Регистрация: 01.06.2013
Сообщений: 4,420
Записей в блоге: 8
01.05.2019, 10:19 8
Цитата Сообщение от Catstail Посмотреть сообщение
[1,0,2,3,5]
Разве кратчайший путь не [1,3,5] ?
1
Catstail
Модератор
24608 / 12515 / 2285
Регистрация: 12.02.2012
Сообщений: 20,334
01.05.2019, 16:33 9
Да, похоже, ошибка у меня. Вот - разлаписто, но работает:

Добавлено через 4 часа 13 минут
Haskell
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
mark :: [Int] -> Int -> Int -> [Int]
mark chk n m | (n == 0) = m : (tail chk)
             | otherwise = (head chk) : (mark (tail chk) (n-1) m)
 
newV :: [[Int]] -> Int -> [Int] -> [Int] -> [Int]
newV g n chk que = (filter (\ x -> (chk !! x) == 0) (g !! n))
 
setP :: [Int] -> Int -> [Int] -> [Int]
setP pth n [] = pth
setP pth n (f:fs) = setP (mark pth f n) n fs
 
bfs' :: [[Int]] -> [Int] -> [Int] -> [Int] -> [Int]
bfs' g [] chk pth  = pth 
bfs' g que chk pth = (bfs' g (tq ++ nV) (setP chk 1 nV) (setP pth hq nV))
                     where tq=(tail que); hq=(head que); nV=(newV g hq chk tq);
 
showPath :: [Int] -> Int -> [Int]
showPath pth n | (pth !! n) == negate 1 = [n]
               | otherwise = n : (showPath pth (pth !! n))
 
bfs :: [[Int]] -> Int -> Int -> [Int]
bfs g start fin = if (start >= k) || (start < 0) || (fin >= k) || (fin < 0) then 
                     error "Bad number of vertex!"
                  else   
                     reverse $ showPath (bfs' g [start] (mark chk start 1) pth) fin 
                  where chk=(take k (repeat 0))
                        pth=(mark chk start (negate 1))
                        k=length g 
 
-- проверка
 
*Main> bfs [[1,2],[0,2,3],[0,1,3,4],[1,2,4,5],[2,3,5],[3,4]] 1 5
[1,3,5]
 
*Main> bfs [[1,2],[0,2,3],[0,1,3,4],[1,2,4,5],[2,3,5],[3,4]] 0 4
[0,2,4]
 
*Main> bfs [[1,2],[0,2,3],[0,1,3,4],[1,2,4,5],[2,3,5],[3,4]] 0 5
[0,1,3,5]
 
*Main> bfs [[1,2],[0,2,3],[0,1,3,4],[1,2,4,5],[2,3,5],[3,4]] 1 4
[1,2,4]
 
*Main> bfs [[1,2],[0,2,3],[0,1,3,4],[1,2,4,5],[2,3,5],[3,4]] 6 4
*** Exception: Bad number of vertex!
 
*Main> bfs [[1,2],[0,2,3],[0,1,3,4],[1,2,4,5],[2,3,5],[3,4]] 4 8
*** Exception: Bad number of vertex!
1
XRuZzz
Антикодер
1614 / 775 / 44
Регистрация: 15.09.2012
Сообщений: 2,888
04.05.2019, 13:03 10
У Липовача в книге, подобная задача рассматривается тут:
LYAH → 10. Functionally Solving Problems → Heathrow to London
1
04.05.2019, 13:03
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.05.2019, 13:03

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

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

Найти все вершины графа, к которым существует путь заданной длины от выделенной вершины графа
Написать программу на prologuse на русском языке как на примере(Определить, является ли связным...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru