{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# \u7b97\u6cd5\u56fe\u89e3 \u2014 \u56fe\u7b97\u6cd5\u7bc7\n", "\n", "\u672c\u7b14\u8bb0\u672c\u662f [grokking_algorithms.html](grokking_algorithms.html) \u4e2d\n", "**\u56fe\u7b97\u6cd5**\u3001**\u7b97\u6cd5\u8303\u5f0f**\u4e0e**\u673a\u5668\u5b66\u4e60**\u4e09\u8282\u7684\u52a8\u624b\u5b9e\u8df5\u7248\u3002\n", "\n", "\u6bcf\u4e2a\u4ee3\u7801\u5355\u5143\u683c\u524d\u9762\u90fd\u6709 **\ud83d\udc0d \u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027** \u8bf4\u660e\uff0c\n", "\u4ee3\u7801\u6bcf\u4e00\u884c\u90fd\u5e26\u6ce8\u91ca\u3002\n", "\n", "**\u672c\u7b14\u8bb0\u672c\u6db5\u76d6\uff1a**\n", "1. \u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\uff08BFS\uff09\n", "2. \u8fea\u6770\u65af\u7279\u62c9\u7b97\u6cd5\n", "3. A* \u641c\u7d22\n", "4. \u8d2a\u5fc3 \u2014\u2014 \u96c6\u5408\u8986\u76d6\n", "5. \u52a8\u6001\u89c4\u5212 \u2014\u2014 \u5e26\u8bb0\u5fc6\u5316\u7684\u6590\u6ce2\u90a3\u5951\n", "6. k-\u8fd1\u90bb" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. \u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\n", "\n", "BFS \u6309\u5c42\u63a2\u7d22\u56fe \u2014\u2014 \u5148\u8bbf\u95ee\u76f4\u63a5\u670b\u53cb\uff0c\u518d\u8bbf\u95ee\u670b\u53cb\u7684\u670b\u53cb\u3002\n", "**\u961f\u5217**\uff08\u5148\u8fdb\u5148\u51fa\uff09\u51b3\u5b9a\u8bbf\u95ee\u987a\u5e8f\u3002\u5728\u65e0\u6743\u56fe\u4e0a\u80fd\u627e\u5230\u8fb9\u6570\u6700\u5c11\u7684\u6700\u77ed\u8def\u5f84\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `from collections import deque` \u5bfc\u5165 `deque` \u2014\u2014 \u53cc\u7aef\u961f\u5217\uff0cappend \u548c popleft \u90fd\u662f O(1)\u3002`deque([start])` \u521b\u5efa\u5305\u542b\u4e00\u4e2a\u5143\u7d20\u7684deque\u3002`{start}` \u662f\u53ea\u6709\u4e00\u4e2a\u5143\u7d20\u7684\u96c6\u5408\u3002\u96c6\u5408\u67e5\u8be2\uff08`x in seen`\uff09\u5e73\u5747 O(1)\uff0c\u7279\u522b\u9002\u5408\u8bb0\u5f55\u5df2\u8bbf\u95ee\u8282\u70b9\u3002`dict` \u6620\u5c04 `\u952e \u2192 \u5217\u8868` \u662f\u4e00\u79cd\u5e38\u89c1\u7684\u56fe\u8868\u793a\u65b9\u5f0f\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from collections import deque\n", "\n", "graph = { # \u90bb\u63a5\u8868\uff1a\u540d\u5b57 \u2192 \u670b\u53cb\u5217\u8868\n", " \"you\": [\"alice\", \"bob\", \"claire\"],\n", " \"alice\": [\"dave\"],\n", " \"bob\": [\"eve\"],\n", " \"claire\": [\"frank\"],\n", " \"dave\": [], \"eve\": [], \"frank\": [],\n", "}\n", "\n", "def bfs(start, target):\n", " queue = deque([start]) # \u4ece\u4e00\u4e2a\u8d77\u70b9\u5f00\u59cb\n", " seen = {start} # \u5df2\u7ecf\u52a0\u5165\u8fc7\u961f\u5217\u7684\u8282\u70b9\n", " while queue: # \u53ea\u8981\u8fd8\u6709\u8282\u70b9\u8981\u8bbf\u95ee\u5c31\u7ee7\u7eed\n", " node = queue.popleft() # \u4ece**\u524d\u9762**\u53d6 \u2014\u2014 \u8fd9\u5c31\u662f BFS\n", " if node == target:\n", " return True\n", " for neighbour in graph[node]:\n", " if neighbour not in seen:\n", " seen.add(neighbour)\n", " queue.append(neighbour) # \u52a0\u5230**\u540e\u9762**\n", " return False # \u80fd\u5230\u8fbe\u7684\u8282\u70b9\u90fd\u8bbf\u95ee\u8fc7\u4e86 \u2014\u2014 \u6ca1\u627e\u5230\n", "\n", "print(\"Find frank:\", bfs(\"you\", \"frank\"))\n", "print(\"Find ghost:\", bfs(\"you\", \"ghost\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### \u540c\u65f6\u8fd4\u56de\u8def\u5f84\u7684 BFS\n", "\n", "\u8bb0\u5f55\u6bcf\u4e2a\u8282\u70b9\u7684\u7236\u8282\u70b9\uff0c\u627e\u5230\u76ee\u6807\u65f6\u53cd\u5411\u91cd\u5efa\u8def\u5f84\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `parent = {start: None}` \u540c\u65f6\u5145\u5f53\u300c\u5df2\u8bbf\u95ee\u300d\u6807\u8bb0\uff08\u952e\u5b58\u5728\u5c31\u8bf4\u660e\u5df2\u5165\u961f\u8fc7\uff09\u548c\u300c\u7236\u8282\u70b9\u6620\u5c04\u300d\u3002`path[::-1]` \u662f\u6b65\u957f -1 \u7684\u5207\u7247\uff0c\u7528\u6765\u53cd\u8f6c\u5217\u8868\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def bfs_path(start, target):\n", " queue = deque([start])\n", " parent = {start: None} # \u8282\u70b9 \u2192 \u8c01\u628a\u5b83\u5165\u961f\u7684\uff08\u8d77\u70b9\u4e3a None\uff09\n", " while queue:\n", " node = queue.popleft()\n", " if node == target:\n", " # \u6cbf parent \u4ece\u76ee\u6807\u8d70\u56de\u8d77\u70b9\n", " path = []\n", " while node is not None:\n", " path.append(node)\n", " node = parent[node]\n", " return path[::-1] # \u53cd\u8f6c\u540e\u5373\u4ece\u8d77\u70b9 \u2192 \u76ee\u6807\n", " for neighbour in graph[node]:\n", " if neighbour not in parent:\n", " parent[neighbour] = node # \u8bb0\u5f55\u662f\u8c01\u628a\u8fd9\u4e2a\u90bb\u5c45\u5165\u961f\u7684\n", " queue.append(neighbour)\n", " return None # \u4e0d\u5b58\u5728\u901a\u8def\n", "\n", "print(\"Path to frank:\", bfs_path(\"you\", \"frank\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**\u8bd5\u4e00\u8bd5 \u2014\u2014 \u53ea\u6362\u4e00\u884c\u5c31\u53d8\u6210 DFS\u3002**\u628a `queue.popleft()` \u6539\u6210 `queue.pop()`\n", "\uff08\u4ece*\u672b\u5c3e*\u53d6\uff09\u3002BFS \u7acb\u523b\u53d8\u6210 DFS\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. \u8fea\u6770\u65af\u7279\u62c9\u7b97\u6cd5\n", "\n", "\u5f53\u8fb9\u6709\u6743\u91cd\u65f6\uff0cBFS \u4e0d\u518d\u80fd\u7ed9\u51fa\u4ee3\u4ef7\u6700\u4f4e\u7684\u8def\u5f84\u3002\u8fea\u6770\u65af\u7279\u62c9\u628a BFS \u7684\"\n", "\"\u961f\u5217\u6362\u6210\u6309\u603b\u4ee3\u4ef7\u6392\u5e8f\u7684**\u4f18\u5148\u961f\u5217**\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `float(\"inf\")` \u662f\u300c\u8fd8\u4e0d\u77e5\u9053\u8def\u5f84\u300d\u7684\u5360\u4f4d\u7b26 \u2014\u2014 \u4efb\u4f55\u6570\u90fd\u6bd4\u5b83\u5c0f\u3002\u5b57\u5178\u63a8\u5bfc\u5f0f `{k: v for k in iterable}` \u6784\u9020\u5b57\u5178\u3002\u6211\u4eec\u5f80\u5806\u91cc push `(\u8ddd\u79bb, \u8282\u70b9)` \u5143\u7ec4\uff0c\u8ba9\u5806\u6309\u8ddd\u79bb\u6392\u5e8f\u3002`dict.items()` \u5728\u904d\u5386\u65f6\u540c\u65f6\u7ed9\u51fa `(\u952e, \u503c)`\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import heapq\n", "\n", "def dijkstra(graph, source):\n", " distances = {node: float(\"inf\") for node in graph} # \u5168\u90e8\u521d\u59cb\u5316\u4e3a\"\u672a\u77e5\"\n", " distances[source] = 0\n", " pq = [(0, source)] # (\u8ddd\u79bb, \u8282\u70b9) \u7684\u5806\n", "\n", " while pq:\n", " d, u = heapq.heappop(pq) # \u5f53\u524d\u8ddd\u79bb\u6700\u5c0f\u7684\u672a\u8bbf\u95ee\u8282\u70b9\n", " if d > distances[u]:\n", " continue # \u8fc7\u671f\u9879 \u2014\u2014 \u5df2\u627e\u5230\u66f4\u77ed\uff0c\u8df3\u8fc7\n", " for v, weight in graph[u].items():\n", " alt = d + weight # \u7ecf\u8fc7 u \u5230 v \u7684\u4ee3\u4ef7\n", " if alt < distances[v]:\n", " distances[v] = alt # \u66f4\u65b0\u4e3a\u66f4\u77ed\u7684\u8ddd\u79bb\n", " heapq.heappush(pq, (alt, v))\n", " return distances\n", "\n", "# \u5c0f\u578b\u5e26\u6743\u56fe\uff1adict \u5d4c dict\u3002\n", "graph = {\n", " \"start\": {\"a\": 6, \"b\": 2},\n", " \"a\": {\"end\": 1},\n", " \"b\": {\"a\": 3, \"end\": 5},\n", " \"end\": {},\n", "}\n", "print(dijkstra(graph, \"start\"))\n", "# start \u2192 end \u6700\u4f4e\u4ee3\u4ef7 6\uff1astart \u2192 b (2) \u2192 a (3) \u2192 end (1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**\u8bd5\u4e00\u8bd5\uff1a**\u628a `start \u2192 b` \u7684\u6743\u91cd\u4ece 2 \u6539\u6210 10\u3002\u6700\u4f4e\u4ee3\u4ef7\u8def\u5f84\n", "\u4f1a\u53d8 \u2014\u2014 \u8fea\u6770\u65af\u7279\u62c9\u4f1a\u6539\u8d70\u7ecf\u8fc7 `a` \u7684\u8def\u3002\u4fee\u6539\u540e\u91cd\u65b0\u8fd0\u884c\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. A* \u641c\u7d22\n", "\n", "\u8fea\u6770\u65af\u7279\u62c9\u52a0\u4e00\u4e2a\u542f\u53d1\u51fd\u6570\u3002\u8fea\u6770\u65af\u7279\u62c9\u9009 `g(n)`\uff08\u5df2\u8d70\u4ee3\u4ef7\uff09\u6700\u5c0f\u7684\u8282\u70b9\uff0c\n", "A* \u9009 `f(n) = g(n) + h(n)`\uff08\u5df2\u8d70 + \u4f30\u8ba1\u5269\u4f59\uff09\u6700\u5c0f\u7684\u8282\u70b9\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `abs(x)` \u53d6\u7edd\u5bf9\u503c\u3002\u50cf `(0, 0)` \u8fd9\u6837\u7684\u5143\u7ec4\u5f88\u9002\u5408\u4f5c\u7f51\u683c\u5750\u6807 \u2014\u2014 \u5b83\u4eec\u53ef\u54c8\u5e0c\uff0c\u80fd\u653e\u8fdb set \u548c dict\u3002`dict.get(\u952e, \u9ed8\u8ba4\u503c)` \u8bfb\u53d6\u503c\uff0c\u5982\u679c\u952e\u7f3a\u5931\u5c31\u8fd4\u56de\u9ed8\u8ba4\u503c \u2014\u2014 \u9002\u5408\u300c\u8fd8\u6ca1\u770b\u8fc7 = \u65e0\u7a77\u4ee3\u4ef7\u300d\u7684\u573a\u666f\u3002`_` \u662f\u7ea6\u5b9a\u4fd7\u6210\u7684\u300c\u6211\u4e0d\u5173\u5fc3\u8fd9\u4e2a\u503c\u300d\u7684\u53d8\u91cf\u540d\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import heapq\n", "\n", "def manhattan(a, b):\n", " # \u66fc\u54c8\u987f\u8ddd\u79bb\uff1a\u5404\u5750\u6807\u5dee\u7684\u7edd\u5bf9\u503c\u4e4b\u548c\n", " return abs(a[0] - b[0]) + abs(a[1] - b[1])\n", "\n", "def a_star(start, goal, walkable):\n", " open_set = [(manhattan(start, goal), 0, start)] # \u5806\u5143\u7d20 (f, g, \u8282\u70b9)\n", " best_g = {start: 0} # \u6bcf\u4e2a\u8282\u70b9\u5df2\u77e5\u7684\u6700\u5c0f g\n", "\n", " while open_set:\n", " _, g, current = heapq.heappop(open_set) # f \u6700\u5c0f\u7684\u8282\u70b9\n", " if current == goal:\n", " return g # \u5230\u8fbe\u76ee\u6807 \u2014\u2014 \u8fd4\u56de\u603b\u4ee3\u4ef7\n", " for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]: # \u4e0a\u4e0b\u5de6\u53f3\n", " nxt = (current[0] + dx, current[1] + dy)\n", " if nxt not in walkable:\n", " continue # \u649e\u5899\u6216\u8d8a\u754c\n", " tentative = g + 1 # \u6bcf\u6b65\u4ee3\u4ef7\u4e3a 1\n", " if tentative < best_g.get(nxt, float(\"inf\")):\n", " best_g[nxt] = tentative # \u627e\u5230\u4e86\u5230 nxt \u7684\u66f4\u77ed\u8def\u5f84\n", " f = tentative + manhattan(nxt, goal)\n", " heapq.heappush(open_set, (f, tentative, nxt))\n", " return None # \u80fd\u5230\u7684\u683c\u5b50\u90fd\u8bd5\u8fc7\u4e86 \u2014\u2014 \u6ca1\u6709\u8def\u5f84\n", "\n", "# 3\u00d73 \u7f51\u683c\uff0c(0, 1) \u6709\u5899\n", "walkable = {(0,0), (1,0), (1,1), (1,2), (0,2)}\n", "print(\"Path cost:\", a_star((0,0), (0,2), walkable)) # 4" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### \u66f4\u5927\u7684\u7f51\u683c \u2014\u2014 \u770b A* \u7ed5\u5f00\u5899" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** \u96c6\u5408\u63a8\u5bfc\u5f0f\u53ef\u4ee5\u5d4c\u5957\u5faa\u73af\u5e76\u9644\u52a0\u6761\u4ef6\uff0c\u8bed\u6cd5\u8ddf\u5217\u8868\u63a8\u5bfc\u5f0f\u4e00\u6837\u3002`range(7)` \u7ed9\u51fa 0..6\u3002\u7f51\u683c\u5c31\u662f\u4e00\u4e2a (\u884c, \u5217) \u5143\u7ec4\u7684\u96c6\u5408\uff0c\u4ee3\u8868\u53ef\u901a\u884c\u7684\u683c\u5b50\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def build_grid(width, height, walls):\n", " # \u53ef\u901a\u884c = \u9664\u5899\u4ee5\u5916\u7684\u6240\u6709 (r, c)\u3002\n", " return {(r, c) for r in range(height) for c in range(width)\n", " if (r, c) not in walls}\n", "\n", "walls = {(r, 3) for r in range(6)} # \u7b2c 3 \u5217\u3001\u7b2c 0-5 \u884c\u7684\u5899\n", "grid = build_grid(7, 7, walls)\n", "\n", "cost = a_star((0, 0), (6, 6), grid)\n", "print(f\"Cheapest path cost: {cost}\")\n", "\n", "# ASCII \u53ef\u89c6\u5316\n", "for r in range(7):\n", " row = \"\"\n", " for c in range(7):\n", " if (r, c) == (0, 0): row += \" S \"\n", " elif (r, c) == (6, 6): row += \" G \"\n", " elif (r, c) in walls: row += \" \u2593 \"\n", " else: row += \" . \"\n", " print(row)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 4. \u8d2a\u5fc3 \u2014\u2014 \u96c6\u5408\u8986\u76d6\n", "\n", "\u6bcf\u4e00\u6b65\u90fd\u62ff\u5f53\u4e0b\u6700\u597d\u7684\u9009\u9879\u3002\u66f4\u591a\u65f6\u5019\u53ea\u662f\u975e\u5e38\u597d\u7684\u8fd1\u4f3c\u89e3 \u2014\u2014 \u4f46\u627e\u5230\n", "\u771f\u6b63\u6700\u4f18\u89e3\u53ef\u80fd\u8981\u82b1\u4e0a\u51e0\u4e2a\u4e16\u7eaa\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `{...}`\uff08\u91cc\u9762\u662f\u5143\u7d20\uff0c\u4e0d\u662f\u952e:\u503c\uff09\u662f\u96c6\u5408\u5b57\u9762\u91cf\u3002`set1 & set2` \u662f\u96c6\u5408**\u4ea4\u96c6** \u2014\u2014 \u540c\u65f6\u5c5e\u4e8e\u4e24\u8005\u7684\u5143\u7d20\u3002`set1 -= set2` \u539f\u5730\u4ece set1 \u91cc\u5220\u6389 set2 \u7684\u6240\u6709\u5143\u7d20\u3002\u904d\u5386 dict \u9ed8\u8ba4\u5f97\u5230\u952e\uff1b`dict.items()` \u540c\u65f6\u7ed9\u51fa `(\u952e, \u503c)`\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "states_needed = {\"mt\", \"wa\", \"or\", \"id\", \"nv\", \"ut\", \"ca\", \"az\"}\n", "stations = {\n", " \"kone\": {\"id\", \"nv\", \"ut\"},\n", " \"ktwo\": {\"wa\", \"id\", \"mt\"},\n", " \"kthree\": {\"or\", \"nv\", \"ca\"},\n", " \"kfour\": {\"nv\", \"ut\"},\n", " \"kfive\": {\"ca\", \"az\"},\n", "}\n", "\n", "def greedy_set_cover(universe, sets):\n", " still_needed = set(universe) # \u590d\u5236\u4e00\u4efd\u907f\u514d\u4fee\u6539\u8c03\u7528\u8005\u7684\u96c6\u5408\n", " chosen = []\n", " while still_needed:\n", " best_name, best_cover = None, set()\n", " for name, members in sets.items(): # \u8bd5\u6bcf\u4e00\u4e2a\u5019\u9009\u96c6\n", " covered = still_needed & members # \u5b83\u80fd\u8986\u76d6\u591a\u5c11\u8fd8\u9700\u8981\u7684\u5dde\n", " if len(covered) > len(best_cover):\n", " best_name, best_cover = name, covered\n", " if not best_name:\n", " return None # \u65e0\u89e3 \u2014\u2014 \u6ca1\u6709\u4efb\u4f55\u96c6\u80fd\u8986\u76d6\u65b0\u7684\u5dde\n", " chosen.append(best_name)\n", " still_needed -= best_cover # \u5220\u6389\u521a\u8986\u76d6\u7684\u5dde\n", " return chosen\n", "\n", "print(greedy_set_cover(states_needed, stations))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**\u8bd5\u4e00\u8bd5 \u2014\u2014 \u8d2a\u5fc3\u4e5f\u4f1a\u5931\u8d25\u3002**\u9762\u503c [1, 3, 4] \u5206\u7684\u627e\u96f6\u94b1\uff1a\n", "\u8d2a\u5fc3\u7b97\u6cd5\u51d1 6 \u5206\u4f1a\u53d6 4+1+1 = 3 \u679a\uff0c\u6700\u4f18\u89e3\u662f 3+3 = 2 \u679a\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `sorted(coins, reverse=True)` \u8fd4\u56de\u4ece\u5927\u5230\u5c0f\u6392\u5e8f\u7684\u65b0\u5217\u8868\u3002`while target >= c:` \u53ea\u8981\u5f53\u524d\u786c\u5e01\u8fd8\u80fd\u7528\u5c31\u4e00\u76f4\u7528\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def greedy_coins(target, coins):\n", " coins = sorted(coins, reverse=True) # \u4f18\u5148\u5c1d\u8bd5\u5927\u9762\u989d\n", " chosen = []\n", " for c in coins:\n", " while target >= c: # \u8fd9\u679a\u786c\u5e01\u80fd\u7528\u5c31\u4e00\u76f4\u7528\n", " chosen.append(c)\n", " target -= c\n", " return chosen if target == 0 else None # \u51d1\u4e0d\u51fa\u6574\u6570\u5c31\u8fd4\u56de None\n", "\n", "print(\"Make 6 with [1,3,4]:\", greedy_coins(6, [1, 3, 4]))\n", "# \u8d2a\u5fc3 \u2192 4+1+1\uff083 \u679a\uff09\u3002\u6700\u4f18 3+3\uff082 \u679a\uff09\u3002\u8d2a\u5fc3\u5728\u6b64\u5931\u8d25\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 5. \u52a8\u6001\u89c4\u5212 \u2014\u2014 \u6590\u6ce2\u90a3\u5951\n", "\n", "\u6734\u7d20\u9012\u5f52\u7684\u6590\u6ce2\u90a3\u5951\u662f O(2\u207f)\uff0c\u56e0\u4e3a\u540c\u6837\u7684\u6570\u5b57\u88ab\u91cd\u590d\u8ba1\u7b97\u6307\u6570\u6b21\u3002\n", "\u8bb0\u5fc6\u5316\u7248\u672c\u662f O(n)\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** \u4e24\u4e2a\u51fd\u6570\u5b9a\u4e49\uff0c\u4e24\u79cd\u7b56\u7565\u3002\u9ed8\u8ba4\u53c2\u6570 `memo=None` \u907f\u5f00\u300c\u53ef\u53d8\u9ed8\u8ba4\u53c2\u6570\u300d\u9677\u9631\uff08\u5728\u9996\u6b21\u8c03\u7528\u65f6\u521b\u5efa\u4e00\u4e2a\u5168\u65b0\u7684 dict\uff09\u3002`n in memo` \u6d4b\u8bd5\u5b57\u5178\u952e\u662f\u5426\u5b58\u5728\uff0c\u5e73\u5747 O(1)\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# \u6734\u7d20\u7248 \u2014\u2014 \u91cd\u590d\u8ba1\u7b97\u6240\u6709\u4e1c\u897f\uff0c\u6307\u6570\u7ea7\u6162\u3002\n", "def fib_naive(n):\n", " if n < 2:\n", " return n # fib(0)=0, fib(1)=1\n", " return fib_naive(n - 1) + fib_naive(n - 2)\n", "\n", "# \u8bb0\u5fc6\u5316\u7248 \u2014\u2014 \u628a\u7b97\u8fc7\u7684\u7ed3\u679c\u8bb0\u4e0b\u6765\u3002\n", "def fib_memo(n, memo=None):\n", " if memo is None:\n", " memo = {} # \u9876\u5c42\u8c03\u7528\u65f6\u65b0\u5efa\u4e00\u4e2a dict\n", " if n < 2:\n", " return n\n", " if n in memo:\n", " return memo[n] # \u7b97\u8fc7\u4e86 \u2014\u2014 \u76f4\u63a5\u8fd4\u56de\u7f13\u5b58\n", " memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)\n", " return memo[n]\n", "\n", "print(\"fib_naive(30):\", fib_naive(30))\n", "print(\"fib_memo(50): \", fib_memo(50)) # n=50 \u6734\u7d20\u7248\u4f1a\u8dd1\u5f88\u4e45" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### \u7ed9\u4e24\u8005\u8ba1\u65f6" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** \u548c\u4e4b\u524d\u4e00\u6837\u7528 `time.perf_counter()`\u3002\u6734\u7d20\u7248\u7528\u6beb\u79d2\u663e\u793a\uff08\u56e0\u4e3a\u6162\uff09\uff0c\u8bb0\u5fc6\u5316\u7248\u7528\u5fae\u79d2\u663e\u793a\uff08\u56e0\u4e3a\u5feb\uff09\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import time\n", "\n", "for n in [20, 25, 30, 35]:\n", " t0 = time.perf_counter()\n", " fib_naive(n)\n", " naive_time = time.perf_counter() - t0\n", " t0 = time.perf_counter()\n", " fib_memo(n)\n", " memo_time = time.perf_counter() - t0\n", " print(f\"n={n:>3} naive: {naive_time*1000:>8.1f} ms memo: {memo_time*1e6:>6.1f} \u00b5s\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Python \u7684\u4e00\u884c\u7b80\u5199\n", "\n", "`@functools.cache` \u5e2e\u4f60\u505a\u5b8c\u8bb0\u5fc6\u5316 \u2014\u2014 \u4e0d\u9700\u8981\u624b\u52a8\u7ef4\u62a4\u5b57\u5178\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** \u88c5\u9970\u5668\uff08\u51fd\u6570\u4e0a\u9762\u7684 `@cache`\uff09\u4f1a\u5305\u88c5\u51fd\u6570\u3002`@cache` \u628a\u6bcf\u4e2a\uff08\u53c2\u6570 \u2192 \u7ed3\u679c\uff09\u8bb0\u4e0b\u6765\uff0c\u91cd\u590d\u8c03\u7528\u76f4\u63a5\u8fd4\u56de\u7f13\u5b58\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from functools import cache\n", "\n", "@cache # \u88c5\u9970\u5668 \u2014\u2014 \u7ed9 fib() \u52a0\u4e0a\u7f13\u5b58\n", "def fib(n):\n", " if n < 2:\n", " return n\n", " return fib(n - 1) + fib(n - 2)\n", "\n", "print(fib(100)) # \u5de8\u5927\u7684\u6570\uff0c\u77ac\u95f4\u51fa\u6765" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 6. k-\u8fd1\u90bb\n", "\n", "\u7ed9\u4e00\u4e2a\u65b0\u70b9\u8d34\u6807\u7b7e\u7684\u65b9\u6cd5\uff1a\u627e\u5230 k \u4e2a\u6700\u8fd1\u7684\u5df2\u77e5\u6807\u7b7e\u7684\u70b9\uff0c\u8ba9\u5b83\u4eec\u6295\u7968\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `math.sqrt(x)` \u662f\u5f00\u5e73\u65b9\u3002`zip(a, b)` \u628a a \u548c b \u7684\u5143\u7d20\u914d\u5bf9\uff1a`zip([1,2], [10,20])` \u2192 `[(1,10), (2,20)]`\u3002`sum(\u751f\u6210\u5668)` \u628a\u751f\u6210\u5668\u4ea7\u751f\u7684\u6240\u6709\u503c\u52a0\u8d77\u6765\u3002`sorted(seq, key=fn)` \u6309 `fn(\u9879)` \u505a\u6392\u5e8f\u952e\u3002`lambda x: x[0]` \u662f\u8fd4\u56de\u7b2c\u4e00\u4e2a\u5143\u7d20\u7684\u5c0f\u578b\u533f\u540d\u51fd\u6570\u3002`Counter.most_common(1)[0][0]` \u53d6\u51fa\u51fa\u73b0\u6b21\u6570\u6700\u591a\u7684\u90a3\u4e00\u9879\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import math\n", "from collections import Counter\n", "\n", "def knn_predict(train, new_point, k=3):\n", " distances = []\n", " for features, label in train:\n", " # \u6b27\u6c0f\u8ddd\u79bb\uff1a\u6bcf\u4e2a\u5750\u6807\u5dee\u7684\u5e73\u65b9\u4e4b\u548c\uff0c\u518d\u5f00\u5e73\u65b9\n", " d = math.sqrt(sum((a - b) ** 2 for a, b in zip(features, new_point)))\n", " distances.append((d, label))\n", " distances.sort(key=lambda x: x[0]) # \u6309\u8ddd\u79bb\uff08\u7b2c\u4e00\u4e2a\u5143\u7d20\uff09\u6392\u5e8f\n", " k_labels = [label for _, label in distances[:k]] # \u6700\u8fd1 k \u4e2a\u7684\u6807\u7b7e\n", " return Counter(k_labels).most_common(1)[0][0] # \u591a\u6570\u6295\u7968\n", "\n", "# \u7279\u5f81\uff1a(\u91cd\u91cf\u514b, \u76f4\u5f84\u5398\u7c73)\n", "train = [\n", " ((150, 8), \"apple\"),\n", " ((170, 9), \"apple\"),\n", " ((140, 7), \"orange\"),\n", " ((130, 6), \"orange\"),\n", "]\n", "print(\"Mystery fruit (145, 7.5):\", knn_predict(train, (145, 7.5), k=3))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**\u8bd5\u4e00\u8bd5 \u2014\u2014 \u6539\u53d8 k \u4f1a\u600e\u6837\uff1f**k=1 \u65f6\u53ea\u770b\u6700\u8fd1\u7684\u90a3\u4e00\u4e2a\u70b9\u3002k=4 \u65f6\n", "*\u5168\u90e8*\u70b9\u90fd\u6295\u7968\u3002\u8bd5\u8bd5\u51e0\u4e2a\u4e0d\u540c\u7684 k\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** \u7528\u7684\u662f\u4e0a\u9762\u7684 `knn_predict()` \u2014\u2014 \u8fd9\u91cc\u53ea\u662f\u5728\u5faa\u73af\u91cc\u7528\u4e0d\u540c\u7684 k \u8c03\u7528\u5b83\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for k in [1, 2, 3, 4]:\n", " pred = knn_predict(train, (145, 7.5), k=k)\n", " print(f\"k={k}: {pred}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### \u7279\u5f81\u7f29\u653e \u2014\u2014 \u4e3a\u4ec0\u4e48\u91cd\u8981\n", "\n", "\u91cd\u91cf\u7528\u514b\uff08150\uff09\u3001\u76f4\u5f84\u7528\u7c73\uff080.08\uff09\uff0c\u8ddd\u79bb\u4f1a\u88ab\u91cd\u91cf\u5b8c\u5168\u4e3b\u5bfc \u2014\u2014\n", "\u76f4\u5f84\u51e0\u4e4e\u6ca1\u8d21\u732e\u3002\u5148\u505a\u5f52\u4e00\u5316\u3002" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** Z-\u5206\u6570\u5f52\u4e00\u5316\uff1a\u51cf\u53bb\u5747\u503c\uff0c\u518d\u9664\u4ee5\u6807\u51c6\u5dee\u3002\u6211\u4eec\u81ea\u5df1\u8ba1\u7b97\u5747\u503c\u548c\u6807\u51c6\u5dee\uff0c\u4e0d\u7528 numpy\u3002`**` \u662f\u5e42\u8fd0\u7b97\uff1a`x ** 2` \u662f\u5e73\u65b9\uff0c`x ** 0.5` \u662f\u5f00\u5e73\u65b9\u3002" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# \u540c\u6837\u7684\u6c34\u679c\u4f46\u76f4\u5f84\u7528**\u7c73**\u800c\u4e0d\u662f\u5398\u7c73 \u2014\u2014 \u8ddd\u79bb\u88ab\u4e25\u91cd\u626d\u66f2\u3002\n", "bad_train = [\n", " ((150, 0.08), \"apple\"),\n", " ((170, 0.09), \"apple\"),\n", " ((140, 0.07), \"orange\"),\n", " ((130, 0.06), \"orange\"),\n", "]\n", "# \u795e\u79d8\u6c34\u679c 145 g, 0.075 m\n", "print(\"With raw mixed units:\", knn_predict(bad_train, (145, 0.075), k=3))\n", "\n", "# \u5bf9\u6bcf\u4e2a\u7279\u5f81\u72ec\u7acb\u505a z-\u5206\u6570\u5f52\u4e00\u5316\u3002\n", "def zscore(values):\n", " mean = sum(values) / len(values)\n", " std = (sum((v - mean) ** 2 for v in values) / len(values)) ** 0.5\n", " return [(v - mean) / std for v in values], mean, std\n", "\n", "weights, w_mean, w_std = zscore([w for (w, _), _ in bad_train])\n", "diams, d_mean, d_std = zscore([d for (_, d), _ in bad_train])\n", "scaled_train = [((w, d), label) for (w, d), (_, label) in zip(zip(weights, diams), bad_train)]\n", "scaled_query = ((145 - w_mean) / w_std, (0.075 - d_mean) / d_std)\n", "\n", "print(\"With z-score normalization:\", knn_predict(scaled_train, scaled_query, k=3))" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.x" } }, "nbformat": 4, "nbformat_minor": 5 }