貪心演算法之——黑白點的匹配(兩種實現方法)

来源:https://www.cnblogs.com/Unicron/archive/2019/09/23/11574652.html
-Advertisement-
Play Games

一、題目 設平面上分佈著n個白點和n個黑點,每個點用一對坐標(x, y)表示。一個黑點b=(xb,yb)支配一個白點w=(xw, yw)當且僅當xb>=xw和yb>=yw。 若黑點b支配白點w,則黑點b和白點w可匹配(可形成一個匹配對)。 在一個黑點最多只能與一個白點匹配,一個白點最多只能與一個黑點 ...


一、題目

設平面上分佈著n個白點和n個黑點,每個點用一對坐標(x, y)表示。一個黑點b=(xb,yb)支配一個白點w=(xw, yw)當且僅當xb>=xw和yb>=yw。

若黑點b支配白點w,則黑點b和白點w可匹配(可形成一個匹配對)。

在一個黑點最多只能與一個白點匹配,一個白點最多只能與一個黑點匹配的前提下,求n個白點和n個黑點的最大匹配對數。

 

二、解題思路

  一看完題目,一開始的思路是先將黑白點分別存入兩個數組中,再對兩個數組分別進行對x和對y的排序,在實際實驗過程中,發現排序完後數組的下標與點不好對應,這樣就不容易確定一個點是否已經匹配過。

  經過瞭解查閱後發現了最大匹配問題的演算法,和本題類似,而且遞歸的操作複雜度遠小於多次對數組的排序。

  而且過多的排序也造成了演算法思路難以理清。決定先學習掌握最大匹配度演算法再考慮本題…

  在查閱了最大匹配度問題的思想後,發現這是一種遞歸形式的方法,演算法需要基於對二分圖的遍歷演算法,這就需要學習DFS或者BFS,所以又去複習了一下這兩個演算法,在徹底掌握了之後終於可以步入正題了…

(dfs和bfs的執行動態圖

http://5b0988e595225.cdn.sohucs.com/images/20171101/f1f45fe9ca37425ba200180be89624b2.gif

http://5b0988e595225.cdn.sohucs.com/images/20171101/a85c0716fcc847f1915dddfcfd019c01.gif

 

理解了最大匹配演算法後,發現只要在圖遍歷的基礎上,多藉助一個matching數組,用來儲存各匹配點之間的聯繫,通過一些剪枝和判斷就可以實現。

我選擇了DFS進行最大匹配演算法的基礎演算法,DFS是對圖做出處理,在空間上需要藉助一張鄰接矩陣,我的想法是將黑白點問題化作圖,再根據題目的要求做出對應的鄰接矩陣,這樣再通過最大匹配就可以求解出來。

 

下麵主要針對這兩個問題討論並通過具體例子演示最大匹配核心思想。

1、如何將黑白點化作圖:

創建一個結構體

 

黑白點都看作頂點,只通過color進行區別

2、如何求對應鄰接矩陣:

       對儲存所有頂點的結構體數組做兩次迴圈,若滿足題目中黑點xy坐標大於白點,即將鄰接矩陣該位置置為1。

3、具體流程演示:

 

上圖分析:

通過鄰接表可以知道,2能控制4,7,8三點

一開始2就控制了4,跳過2點

接著5控制了7,跳過5點

6控制了7,但是7已經被5控制,這時回到5,

5控制了8,跳過5

這時7沒人控制,6控制7,流程結束,匹配度為3。

 

三、代碼(DFS BFS兩種實現方法)

  1 public class MaxMatching {// 基於DFS
  2 
  3     static int graph[][]; // 鄰接表 預設全為0
  4     static int n; // 節點數
  5     static int visit[]; // 是否訪問
  6     static int matched[]; // 是否已經匹配,對應的匹配點
  7     static vertex V[];//// 結構體數組儲存所有黑白
  8 
  9     public class vertex {// 頂點結構體
 10         public int color;// 白:0 黑:1
 11         public double Vx;
 12         public double Vy;
 13     }
 14 
 15     public void Init() {
 16         System.out.println("輸入的黑白點總數為:");
 17         Scanner sc = new Scanner(System.in);
 18         n = sc.nextInt();
 19         graph = new int[n][n]; // 鄰接表 預設全為0
 20         visit = new int[n]; // 是否訪問
 21         matched = new int[n]; // 是否已經匹配,對應的匹配點
 22         V = new vertex[n];
 23         InitGraph();// 初始鄰接矩陣
 24     }
 25 
 26     private void InitGraph() {
 27         Scanner sc = new Scanner(System.in);
 28         for (int i = 0; i < n; i++) {// 輸入黑白點
 29             V[i] = new vertex();
 30             System.out.println("please int color/x/y");
 31             V[i].color = sc.nextInt();
 32             V[i].Vx = sc.nextDouble();
 33             V[i].Vy = sc.nextDouble();
 34         }
 35         for (int i = 0; i < n; i++) {
 36             for (int j = 0; j < n; j++) {
 37                 if (i != j && (V[i].color == 1) && (V[j].color == 0) && (V[i].Vx > V[j].Vx) && (V[i].Vy > V[j].Vy)) {
 38                     graph[i][j] = 1;
 39                 }
 40             }
 41         }
 42     }
 43 
 44     // 顯示匹配結果
 45     public void show() {
 46         Arrays.fill(visit, 0);
 47         for (int i = 0; i < n; i++) {
 48             if (visit[i] == 0) {
 49                 if (matched[i] != -1) {
 50                     System.out.println("(" + V[i].Vx + "," + V[i].Vy + ")與" + "(" + V[matched[i]].Vx + ","
 51                             + V[matched[i]].Vy + ")" + "匹配");
 52                     visit[i] = 1;
 53                     visit[matched[i]] = 1;
 54                 }
 55             }
 56         }
 57     }
 58 
 59     /*
 60      * dfs實現, params: x:起始的未匹配點 return: 1:找到增廣路 0:未找到
 61      */
 62     public int dfs_solve(int x) {
 63         // 找到一個和節點存在邊的點,並且該點在本輪中沒有被訪問過
 64         for (int i = 0; i < n; i++) {
 65             if (graph[x][i] != 0 && visit[i] == 0) {
 66                 visit[i] = 1; // 標記為匹配過
 67                 // 按照交替路的模式找增廣路,增廣路相對於交替路的特性是就是,第一個節點和最後一個節點都是未匹配過的節點
 68                 if (matched[i] == -1 || dfs_solve(matched[i]) == 1) { // 直接跳到matched[i]能夠保證匹配邊和未匹配邊交替
 69                     // 說明找到了一個未匹配節點,將所有匹配邊變為未匹配邊,將所有未匹配邊變為匹配邊,這樣匹配邊數會加1,這個交換過程通過回溯實現
 70 
 71                     matched[x] = i;
 72                     matched[i] = x;
 73 
 74                     System.out
 75                             .println("(" + V[x].Vx + "," + V[x].Vy + ") 與 " + "(" + V[i].Vx + "," + V[i].Vy + ")" + "匹配");
 76                     return 1;
 77                 }
 78             }
 79         }
 80         return 0;
 81     }
 82 
 83     public void hungarian1() {
 84         Arrays.fill(matched, -1);
 85         int sum = 0;
 86         for (int i = 0; i < n; i++) {
 87             if (matched[i] == -1) {
 88                 System.out.println("從 " + "(" + V[i].Vx + "," + V[i].Vy + ")" + " 開始匹配");
 89                 Arrays.fill(visit, 0);// 重置瀏覽數組,用來瀏覽鄰接矩陣當前列
 90                 sum += dfs_solve(i);
 91             }
 92         }
 93         System.out.println("\n"+"最後共有 " + sum + " 匹配項");
 94         show();
 95     }
 96 
 97     public static void main(String[] args) {
 98         MaxMatching mm = new MaxMatching();
 99         mm.Init();
100         mm.hungarian1();
101     }
102 }

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 實在不想看JVM了。刷幾道劍指Offer的題,今天就水一水吧,腦子迷糊。 1.二維數組中的查找 在一個二維數組中(每個一維數組的長度相同),每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數,輸入這樣的一個二維數組和一個整數,判斷數組中是否含有該整數。 解題思路: ...
  • 一、題目 二、思路 1、dfs 實驗要求用多種思路完成,所以一開始就沿用了上一個實驗馬走棋盤的思路,添加了鄰接矩陣來記錄有向網的權值。總體思路還是DFS遍歷搜索。 過程剪枝: 1、因為要求為最短路徑,而一般情況總會存在多條可行路徑,在判斷過程中需要走過每一條路徑才能知道該路徑的長度,但如果已知一條可 ...
  • [TOC] 閉包函數 什麼是閉包函數 閉包函數把 閉包函數內的變數 + 閉包函數內部的函數, 這兩者包裹起來,然後通過返回值的形式返回出來。 定義在函數的內函數 該函數體代碼包含對該函數外層作用域中變數的引用 函數外層指的不是全局作用域 上述代碼中,f是一個全局的名字,但f拿到了inner的記憶體地址 ...
  • 我是一個2019畢業的非電腦的畢業生,從大二開始喜歡上Java直到現在一直都在學習,Brid從小就對電腦感興趣,可惜高中的時候不懂事,沒有規劃未來,考上了一所專科學院,然後大一併不能轉專業,現在畢業了沒有找到Java應屆的工作,只能找點其他的做,但是這阻住不了我對Java的喜歡,趁現在工作的晚上 ...
  • “容器”這兩個字很少被 Python 技術文章提起。一看到“容器”,大家想到的多是那頭藍色小鯨魚:Docker,但這篇文章和它沒有任何關係。本文里的容器,是 Python 中的一個抽象概念,是對專門用來裝其他對象的數據類型的統稱。 在 Python 中,有四類最常見的內建容器類型: 列表(list) ...
  • 溫馨提示 請收藏再看。此文篇幅太長,你短時間看不完;此文乾貨太多,錯過太可惜。 示例代碼可以關註 (公眾號)回覆 獲取。 收穫 1. 講解詳細:能讓你掌握使用 及類似校驗工具的各種使用姿勢 2. 內容全面:可以當做知識字典來查詢 what 註意:hibernate validator 與 持久層框架 ...
  • 閑及無聊 又打開了CSDN開始看一看有什麼先進的可以學習的相關帖子,這時看到了一位大神寫的簡歷裝X必備,手寫Spring MVC。 我想這個東西還是有一點意思的 就拜讀了一下大佬的博客 通讀了一遍相關代碼 感覺和我想象中spring的運作流程基本相同 但是我腦海中基本上只有一個非常簡單的基本概念 而 ...
  • 多好,多簡單,多好 ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...