{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Algoritmusok Python nyelven\n",
"\n",
"## 11. Előadás: Algoritmikus gondolkodás\n",
"\n",
"### 2020. május 15."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"![\"drawing\"](\"https://imgs.xkcd.com/comics/automation_2x.png)
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Programkészítés menete\n",
"\n",
"- Feladat értelmezése\n",
"- Tervezés\n",
"- Implementálás\n",
"- Tesztelés\n",
"- Valamit elcsesztünk, vissza egy korábbi ponthoz!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Tervezés\n",
"- Adatszerkezet kitalálása. Milyen adatokat fogok tárolni? Hogyan érdemes őket tárolni? \n",
"- Milyen műveletekre lesz szükségem? Azokat hogyan lehet algoritmussal megvalósítani?\n",
"- Mennyire számít a sebesség? Ha számít, akkor hogyan érhetem el, hogy gyors legyen?\n",
"- Mennyire pontos eredményt szeretnék? Numerikus vs szimbolikus számítás.\n",
"- Objektum orientáltan csináljam vagy procedurálisan, esetleg funkcionálisan? \n",
"- Hogyan lehet ezeket objektum orientáltan megoldani? Milyen osztályokat érdemes elkészíteni?\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Implementálás és tesztelés\n",
" - Apró lépésekben érdemes dolgozni. Kb mindig legyen működő a program.\n",
" - Ne feledjük el, hogy rengeteg mindent már megírtak, érdemes ezt kihasználni.\n",
" - Érdemes kommentekkel ellátni a kódot, és beszédes változóneveket használni, hogy pár nap múlva is érthető legyen. \n",
" - Minden lényegesebb lépés után teszteljünk. \n",
" - Általában az implementálás, a tesztelés és a hibajavítás gyorsan váltogatja egymást. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\"For some people, programming and debugging are the same thing. That is, programming is the process of gradually debugging a program until it does what you want. The idea is that you should start with a program that does something and make small modifications, debugging them as you go, so that you always have a working program.\" (https://runestone.academy/)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Példa 1. Sodoku megoldó\n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"board=np.array( [\n",
" [7,8,0,4,0,0,1,2,0],\n",
" [6,0,0,0,7,5,0,0,9],\n",
" [0,0,0,6,0,1,0,7,8],\n",
" [0,0,7,0,4,0,2,6,0],\n",
" [0,0,1,0,5,0,9,3,0],\n",
" [9,0,4,0,6,0,0,0,5],\n",
" [0,7,0,3,0,0,0,1,2],\n",
" [1,2,0,0,0,0,4,0,0],\n",
" [0,4,9,2,0,6,0,0,0]\n",
"])"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"def print_board(bo):\n",
" for i in range(len(bo)):\n",
" if i % 3 == 0 and i != 0:\n",
" print(\"- - - - - - - - - - - - - \")\n",
"\n",
" for j in range(len(bo[0])):\n",
" if j % 3 == 0 and j != 0:\n",
" print(\" | \", end=\"\")\n",
"\n",
" if j == 8:\n",
" print(bo[i][j])\n",
" else:\n",
" print(str(bo[i][j]) + \" \", end=\"\")"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"7 8 0 | 4 0 0 | 1 2 0\n",
"6 0 0 | 0 7 5 | 0 0 9\n",
"0 0 0 | 6 0 1 | 0 7 8\n",
"- - - - - - - - - - - - - \n",
"0 0 7 | 0 4 0 | 2 6 0\n",
"0 0 1 | 0 5 0 | 9 3 0\n",
"9 0 4 | 0 6 0 | 0 0 5\n",
"- - - - - - - - - - - - - \n",
"0 7 0 | 3 0 0 | 0 1 2\n",
"1 2 0 | 0 0 0 | 4 0 0\n",
"0 4 9 | 2 0 6 | 0 0 0\n"
]
}
],
"source": [
"print_board(board)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"def find_empty(bo):\n",
" for i in range(len(bo)):\n",
" for j in range(len(bo[0])):\n",
" if bo[i][j] == 0:\n",
" return (i, j) \n",
"\n",
" return None"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(0, 2)"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"find_empty(board)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"def valid(bo, num, pos):\n",
" #1-től 9-ig\n",
" if num not in range(1,10):\n",
" return False\n",
" \n",
" if bo[pos[0],pos[1]]!=0:\n",
" return False\n",
" \n",
" # sor\n",
" for i in range(len(bo[0])):\n",
" if bo[pos[0]][i] == num and pos[1] != i:\n",
" return False\n",
"\n",
" # oszlop\n",
" for i in range(len(bo)):\n",
" if bo[i][pos[1]] == num and pos[0] != i:\n",
" return False\n",
"\n",
" # négyzet\n",
" box_x = pos[1] // 3\n",
" box_y = pos[0] // 3\n",
"\n",
" for i in range(box_y*3, box_y*3 + 3):\n",
" for j in range(box_x * 3, box_x*3 + 3):\n",
" if bo[i][j] == num and (i,j) != pos:\n",
" return False\n",
"\n",
" return True"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1 False\n",
"2 False\n",
"3 False\n",
"4 False\n",
"5 False\n",
"6 False\n",
"7 False\n",
"8 True\n",
"9 False\n"
]
}
],
"source": [
"for i in range(1,10):\n",
" print(i,valid(board,i,(1,3)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Az ötlet, hogy próbáljunk végig mindent. A brute force megoldások sokszor lassúak, viszont néha nincs jobb lehetőség. Mire kell figyelni?\n",
"- Az összes eseten végig akarunk menni, de azokból túl sok van, hogy mind tároljuk.\n",
"- Ezért egy sorrendet állítunk föl, és a szerint próbáljuk végig. \n",
"- Tehát azt kell ügyesen megvalósítani, hogy ha egy adott próbálkozásnál tartunk, abból hogyan lehet a következő próbálkozásra áttérni. \n"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [],
"source": [
"# 1. megoldás \n",
"def solve(bo):\n",
" find = find_empty(bo)\n",
" if not find:\n",
" return bo\n",
" \n",
" # lépések listája, éppen mit és hova próbálunk beírni. \n",
" listofsteps=[[bo.copy(),1,find]]\n",
" \n",
" while True:\n",
" # éppen hol tartunk\n",
" lastboard=listofsteps[-1][0]\n",
" lastnum=listofsteps[-1][1]\n",
" lastpos=listofsteps[-1][2]\n",
" \n",
" # ha helyes a próbálkozás, továbblépünk a következő üres mezőre\n",
" if valid(lastboard, lastnum,lastpos):\n",
" newboard=lastboard.copy()\n",
" newboard[ lastpos[0], lastpos[1]]= lastnum\n",
" newfind = find_empty(newboard)\n",
" if not newfind:\n",
" bo[:] =newboard\n",
" return True\n",
" else:\n",
" listofsteps.append([newboard,1,newfind])\n",
" elif lastnum<10:\n",
" listofsteps[-1][1]=listofsteps[-1][1]+1\n",
" else: \n",
" # ha beszoroltunk visszalépünk az egyel korábbi pozícióhoz és ott tekinjük a következő számot \n",
" del listofsteps[-1]\n",
" if len(listofsteps)==0:\n",
" return False\n",
" else:\n",
" listofsteps[-1][1]=listofsteps[-1][1]+1\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"7 8 0 | 4 0 0 | 1 2 0\n",
"6 0 0 | 0 7 5 | 0 0 9\n",
"0 0 0 | 6 0 1 | 0 7 8\n",
"- - - - - - - - - - - - - \n",
"0 0 7 | 0 4 0 | 2 6 0\n",
"0 0 1 | 0 5 0 | 9 3 0\n",
"9 0 4 | 0 6 0 | 0 0 5\n",
"- - - - - - - - - - - - - \n",
"0 7 0 | 3 0 0 | 0 1 2\n",
"1 2 0 | 0 0 0 | 4 0 0\n",
"0 4 9 | 2 0 6 | 0 0 0\n",
"________________________\n",
"7 8 5 | 4 3 9 | 1 2 6\n",
"6 1 2 | 8 7 5 | 3 4 9\n",
"4 9 3 | 6 2 1 | 5 7 8\n",
"- - - - - - - - - - - - - \n",
"8 5 7 | 9 4 3 | 2 6 1\n",
"2 6 1 | 7 5 8 | 9 3 4\n",
"9 3 4 | 1 6 2 | 7 8 5\n",
"- - - - - - - - - - - - - \n",
"5 7 8 | 3 9 4 | 6 1 2\n",
"1 2 6 | 5 8 7 | 4 9 3\n",
"3 4 9 | 2 1 6 | 8 5 7\n"
]
}
],
"source": [
"print_board(board)\n",
"solve(board)\n",
"print(\"________________________\")\n",
"print_board(board)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Második megoldás, rekurzió"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [],
"source": [
"board=np.array( [\n",
" [0,0,0,0,0,0,1,9,0],\n",
" [2,3,0,0,0,0,6,0,0],\n",
" [0,0,0,2,4,0,0,0,0],\n",
" [0,0,0,0,0,0,9,6,0],\n",
" [0,0,0,1,6,0,0,7,0],\n",
" [0,4,8,0,7,0,0,0,0],\n",
" [0,0,1,0,0,3,4,0,5],\n",
" [0,0,9,0,0,8,0,0,0],\n",
" [0,0,6,0,0,5,8,0,0]\n",
"])"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [],
"source": [
"# 2. megoldás, rekurzió\n",
"def solve2(bo):\n",
" find = find_empty(bo)\n",
" if not find:\n",
" return True\n",
" else:\n",
" row, col = find\n",
"\n",
" for i in range(1,10):\n",
" if valid(bo, i, (row, col)):\n",
" bo[row][col] = i\n",
"\n",
" if solve2(bo):\n",
" return True\n",
"\n",
" bo[row][col] = 0\n",
"\n",
" return False"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 0 0 | 0 0 0 | 1 9 0\n",
"2 3 0 | 0 0 0 | 6 0 0\n",
"0 0 0 | 2 4 0 | 0 0 0\n",
"- - - - - - - - - - - - - \n",
"0 0 0 | 0 0 0 | 9 6 0\n",
"0 0 0 | 1 6 0 | 0 7 0\n",
"0 4 8 | 0 7 0 | 0 0 0\n",
"- - - - - - - - - - - - - \n",
"0 0 1 | 0 0 3 | 4 0 5\n",
"0 0 9 | 0 0 8 | 0 0 0\n",
"0 0 6 | 0 0 5 | 8 0 0\n",
"________________________\n",
"8 6 4 | 5 3 7 | 1 9 2\n",
"2 3 5 | 9 8 1 | 6 4 7\n",
"9 1 7 | 2 4 6 | 5 8 3\n",
"- - - - - - - - - - - - - \n",
"1 7 3 | 8 5 2 | 9 6 4\n",
"5 9 2 | 1 6 4 | 3 7 8\n",
"6 4 8 | 3 7 9 | 2 5 1\n",
"- - - - - - - - - - - - - \n",
"7 8 1 | 6 9 3 | 4 2 5\n",
"3 5 9 | 4 2 8 | 7 1 6\n",
"4 2 6 | 7 1 5 | 8 3 9\n"
]
}
],
"source": [
"print_board(board)\n",
"solve2(board)\n",
"print(\"________________________\")\n",
"print_board(board)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"![\"drawing\"](\"https://i.imgur.com/xNNPN0d.jpg\")
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Példa 2. Edmonds Karp\n",
"\n",
"Adott egy folyamfeladat. Keressünk maximális folyamot benne. \n",
"\n",
"\n",
"\n",
"\n",
"Ford Fulkerson algoritmusnak az Edmonds Karp verzióját valósítjuk meg. \n",
"- mindig keresünk egy javító utat, ami mentén tudunk növelni a folyamon\n",
"- ehhez fenntartunk egy segédgráfot, amit mindig frissítünk\n",
"- ha van a segédgráfban javító út, akkor a mentén javítunk. Mindig a legrövidebb javító utat válasszuk. \n",
" \n",
" "
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [],
"source": [
"import collections"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [],
"source": [
"class Iranyitott():\n",
" def __init__(self,graph):\n",
" self.graph=graph\n",
" self.num=len(graph)\n",
" \n",
" def __str__(self):\n",
" return \"\\n\".join([str(x) for x in self.graph])\n",
" \n",
" def bfs(self, s, t, parent):\n",
" visited = [False] * (self.num)\n",
" queue = collections.deque()\n",
" \n",
" # a kezdő csúcsot visitedre állítjuk és a sorba rakjuk \n",
" queue.append(s)\n",
" visited[s] = True\n",
" \n",
" # szoksásos BFS bejárás\n",
" while queue:\n",
" u = queue.popleft()\n",
" # nézzük u szomszédait, ha valamelyiken még nem jártunk, mehet a sorba, és visited-re állítjuk\n",
" for ind, val in enumerate(self.graph[u]):\n",
" if (visited[ind] == False) and (val > 0):\n",
" queue.append(ind)\n",
" visited[ind] = True\n",
" parent[ind] = u\n",
" \n",
" # hal elértünk t-ig akkor igazzal térünk vissza, különben hamis\n",
" return visited[t]\n",
" \n",
" def edmonds_karp(self, source, sink):\n",
" \n",
" # ebben fogjuk tárolni a bfs eredményét\n",
" parent = [-1] * (self.num)\n",
"\n",
" max_flow = 0 \n",
"\n",
" # Amíg van javító út \n",
" while self.bfs (source, sink, parent):\n",
"\n",
" # megnézzük mennyivel tudunk javítani\n",
" path_flow = float(\"Inf\")\n",
" s = sink\n",
" while s != source:\n",
" path_flow = min(path_flow, self.graph[parent[s]][s])\n",
" s = parent[s]\n",
"\n",
" # növeljük a folyam értékét\n",
" max_flow += path_flow\n",
"\n",
" # a javító út mentén javítunk\n",
" v = sink\n",
" while v != source:\n",
" u = parent[v]\n",
" self.graph[u][v] -= path_flow\n",
" self.graph[v][u] += path_flow\n",
" v = parent[v]\n",
"\n",
" return max_flow"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [],
"source": [
"I=Iranyitott( [[0, 16, 13, 0, 0, 0],\n",
" [0, 0, 10, 12, 0, 0],\n",
" [0, 4, 0, 0, 14, 0],\n",
" [0, 0, 9, 0, 0, 20],\n",
" [0, 0, 0, 7, 0, 4],\n",
" [0, 0, 0, 0, 0, 0]])\n"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[0, 16, 13, 0, 0, 0]\n",
"[0, 0, 10, 12, 0, 0]\n",
"[0, 4, 0, 0, 14, 0]\n",
"[0, 0, 9, 0, 0, 20]\n",
"[0, 0, 0, 7, 0, 4]\n",
"[0, 0, 0, 0, 0, 0]\n"
]
}
],
"source": [
"print(I)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"par=dict()\n",
"I.bfs(1,0, [-1] * (I.num))"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"11"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"I.edmonds_karp(4,5)}"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.4"
}
},
"nbformat": 4,
"nbformat_minor": 2
}