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

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

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

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

заранее всем спасибо!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.04.2019, 11:18
Ответы с готовыми решениями:

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

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

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

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

17
Модератор
26268 / 13677 / 2600
Регистрация: 12.02.2012
Сообщений: 22,430
30.04.2019, 11:26 2
Эта формулировка неконкретна. Задача на графы? Как задается граф? Каков его тип? Что за запросы? Только не надо писать: "так в методичке"!
0
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
Модератор
26268 / 13677 / 2600
Регистрация: 12.02.2012
Сообщений: 22,430
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
0 / 0 / 0
Регистрация: 20.03.2018
Сообщений: 7
30.04.2019, 11:58  [ТС] 5
Очень благодарен! буду разбирать что к чему
0
3636 / 2369 / 310
Регистрация: 01.06.2013
Сообщений: 5,058
Записей в блоге: 9
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
Модератор
26268 / 13677 / 2600
Регистрация: 12.02.2012
Сообщений: 22,430
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
3636 / 2369 / 310
Регистрация: 01.06.2013
Сообщений: 5,058
Записей в блоге: 9
01.05.2019, 10:19 8
Цитата Сообщение от Catstail Посмотреть сообщение
[1,0,2,3,5]
Разве кратчайший путь не [1,3,5] ?
1
Модератор
26268 / 13677 / 2600
Регистрация: 12.02.2012
Сообщений: 22,430
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
Антикодер
1844 / 820 / 46
Регистрация: 15.09.2012
Сообщений: 2,959
04.05.2019, 13:03 10
У Липовача в книге, подобная задача рассматривается тут:
LYAH → 10. Functionally Solving Problems → Heathrow to London
1
0 / 0 / 0
Регистрация: 12.10.2017
Сообщений: 2
26.01.2020, 15:24 11
Здравствуйте никто не знает как правильно пишется эта часть программы на Haskell.С уважением , Евгений .

Haskell
1
2
 (n == 0) = m : (tail chk)
             | otherwise = (head chk) : (mark (tail chk) (n-1) m)
0
Модератор
26268 / 13677 / 2600
Регистрация: 12.02.2012
Сообщений: 22,430
26.01.2020, 16:13 12
Вот так и пишется:

Haskell
1
2
3
mark :: [Int] -> Int -> Int -> [Int]
mark chk n m | (n == 0) = m : (tail chk)
             | otherwise = (head chk) : (mark (tail chk) (n-1) m)
1
0 / 0 / 0
Регистрация: 12.10.2017
Сообщений: 2
26.01.2020, 16:54 13
Скажите пожалйста ,вы не могли бы дать сове как сделать программный код уникальным пишу лабораторную работу на такую же тему и просто антиплагиат тогда она не пройдёт.С уважением,Квгений
0
3636 / 2369 / 310
Регистрация: 01.06.2013
Сообщений: 5,058
Записей в блоге: 9
26.01.2020, 17:35 14
Цитата Сообщение от dator12 Посмотреть сообщение
Скажите пожалйста ,вы не могли бы дать сове как сделать программный код уникальным пишу лабораторную работу на такую же тему и просто антиплагиат тогда она не пройдёт.
Ответ очевиден: изучить Haskell (не весь, хотя бы то что в рекомендованном здесь Липоваче), может быть почитать про графы, если так не догадаетесь, и написать самому код который и получится уникальным. То, что вам нужно.
2
Модератор
26268 / 13677 / 2600
Регистрация: 12.02.2012
Сообщений: 22,430
26.01.2020, 19:03 15
dator12, "эх, назола!..." Да переименуй все переменные.
0
3636 / 2369 / 310
Регистрация: 01.06.2013
Сообщений: 5,058
Записей в блоге: 9
26.01.2020, 19:16 16
Цитата Сообщение от Catstail Посмотреть сообщение
Да переименуй все переменные.
Переменных в Haskell нет.
1
Модератор
26268 / 13677 / 2600
Регистрация: 12.02.2012
Сообщений: 22,430
26.01.2020, 20:56 17
Curry, простите. Я имел в виду "имена"
0
Антикодер
1844 / 820 / 46
Регистрация: 15.09.2012
Сообщений: 2,959
27.01.2020, 15:49 18
Чтобы код был уникальный, кроме понимания основ Haskell, нужно понимать алгоритмы поиска кратчайшего пути и чем они отличаются.
Например, алгоритмы Флойда-Уоршела, Дейкстры и т п.
2
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.01.2020, 15:49

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

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

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

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


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

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

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