1. NCCU Academic Hub
  2. Publications
  3. College of Informatics
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 快速生成建構於Web之客製化撮合系統
Rapid Generation of Web-Based Customized Matching Systems
作者 吳儼翰
Wu, Yan Han
貢獻者 陳正佳
Chen, Cheng Chia
吳儼翰
Wu, Yan Han
關鍵詞 邏輯程式語言
撮合配對
JSF2
Answer Set Programming
日期 2018
上傳時間 1-Jun-2018 15:51:53 (UTC+8)
摘要 各式應用領域常會面臨許多撮合(Matching)問題，但當我們有需求時卻往往無法定出好的撮合策略，更遑論找到可實現此策略的電腦化解決方法。本研究希望針對穩定婚姻配對、大學聯考分發、論文審查分配、專題選修等等之類的撮合問題提供各種可行的通用撮合策略，可供使用者依其需求快速選用。而後續提供的支援系統則可據此產生一個以WEB為基礎的客製化專門應用領域撮合系統。
而什麼是撮合呢? 撮合是指有A、B兩群對象，在特定的規則與限制條件下，希望使每一A(B) 群對象可以連結至某些B(A)群對象，而使總體滿意度達到最大。以數學而言，一個A、B兩群間的撮合，就是一個滿足特定條件的A、B兩個集合間的二元關係。撮合類型可能是一對一、一對多、 多對多三種。一對一表示一個A群成員只能跟一個B群成員配對，一對多表示 一個A(B) 群成員能跟多個B(A) 群成員配對，多對多則指一個A群成員能跟多個B群成員配對且一個B群成員也能跟多個A群成員配對。
由於撮合型態與策略具有相當大的分歧性，以專用演算法實做並不實際，因此我們採用ASP(Answer set programming)實做撮合程式。ASP 是一種邏輯編程語言，具有宣告式程式特性，廣泛用於組合性問題的解決上，極適合應用在撮合策略的制定與實做。
在可真正執行撮合程式之前，必須預先建置A、B兩群對象的基本資料，因此我們的系統將允許開發者輸入A、B兩群對象的基本後設資料及撮合策略，而系統將據此建立對應Web介面與資料庫，允許使用者建立撮合對象的基本資料。一旦基本資料建立完成，系統即可依據系統設定的撮合策略以及以ASP實做的基本配對規則快速產生撮合結果，提供給使用者參考。
There are a lot of application domains in which we may encounter the problem of finding a matching among two parties of entities. However, it is often the case that once a matching is needed, we cannot easily find a good matching strategy suitable for our purpose, not to mention one with a computerized implementation. This thesis aims to provide a web-based matching generation system allowing the quick generation of customized matching systems for users` need after their input of different demands of matching types and strategies. The supported types of matchings include most often used cases such as marriage/dating matching, paper review assignment, college admission dispatch and student-advisor selection etc.
What is a matching? A (bipartite) matching problem contains two parties of entities, each member of which has a preference over members of the opposite party. A matching in a matching problem is a binary relation between both parties of entities. The goal of a matching problem is to find one or more optimal matching in which the total satisfaction of both party members is maximized. Matching problems can be classified according restrictions imposed on matchings. 1-1 matching requires each member of both parties to be matched to at most one opposite party member, 1-m matching allows only members of one party to be matched to more than one opposite party member, and m-m matching allows members of both parties to be matched to more than one opposite party member.
Because there is a great variety of matching types and strategies, it is impractical to employ dedicated algorithm per case. It is thus eagerly expected to have a general framework in which different types of matching and strategies can be encoded. By applying Answer-set Programming (ASP) we provided one such framework in this thesis. ASP is logic programming language with declarative characteristics, widely applied in the solution of hard combinatorial problems, to be used in the encoding and solving of matching problems with different preference matching strategies.
Theoretical discussion of matching algorithms always assumes that party members and their preferences are available in advance. However, to engineer a matching system, we still need to provide means to achieve it. Our system is thus also a matching support system, through the web interface of which developers and end-users can enter meta and individual information about all concerned properties and/or preferences of party members. After a possibly further processing of users` preference on the values of concerned properties of opposite party members for deriving every member`s preference on the member of the opposite party, succeeding matching thus can obtain all needed data.
參考文獻 [1] Ajax. Retrieved May (2017). From https://zh.wikipedia.org/wiki/AJAX
[2] Alvin E. Roth, Tayfun Sonmez, & M. Utku Unver. (2004). Kidney Exchange, The Quarterly Journal of Economics, vol. 119, no. 2, pp. 457-488.
[3] Bipartite Matching. Retrieved May (2017). From http://www.csie.ntnu.edu.tw/~u91029/Matching.html#2
[4] Derby. Retrieved May (2017). From http://db.apache.org/derby/docs/10.6/ref/
[5] DLV - User Manual. Retrieved May (2017). From http://www.dlvsystem.com/html/DLV_User_Manual.html
[6] DLV Wrapper. Retrieved May (2017). From http://www.dlvsystem.com/dlvwrapper/#1
[7] Ed Burns, Chris, Schalk, & Neil Griffin. (2009). Java Server Faces 2.0 the Complete Reference.
[8] Faces Event. Retrieved May (2017). From http://openhome.cc/Gossip/JSF/ValueChangeEvents.htm
[9] FacesServlet. Retrieved May (2017). From https://docs.oracle.com/javaee/7/api/javax/faces/webapp/FacesServlet.html
[10] Gale-Shapley algorithm. Retrieved May (2017). From https://en.wikipedia.org/wiki/Stable_marriage_problem
[11] Irving, R.W. and Manlove, D.F. and O`Malley, G. (2009). Stable Marriage with Ties and Bounded Length Preference Lists. Journal of Discrete Algorithms, vol. 7, no. 2, pp. 213-219.
[12] Java Database Connectivity. Retrieved May (2017). From http://openhome.cc/Gossip/JavaGossip-V2/IntroduceJDBC.htm
[13] JSF Lifecycle. Retrieved May (2017). From http://www.w3ii.com/zh-TW/jsf/jsf_life_cycle.html
[14] Martin Gebser, Roland Kaminski, Benjamin Kaufmann, Marius Lindauer, Max Ostrowski, Javier Romero, Torsten Schaub, & Sven Thiele. (2017). Potassco User Guide 2.1.0 From https://github.com/potassco/guide/releases/
[15] Mario Alviano, Wolfgang Faber, Nicola Leone, Simona Perri, Gerald Pfeifer, & Giorgio Terracina. (2010). The Disjunctive Datalog System DLV, Proceedings of the First International Conference on Datalog Reloaded, pp. 282-301.
[16] Michael Gelfond, & Yulia Kahl. (2014).Knowledge Representation, Reasoning, and the Design of Intelligent Agents.
[17] Model-View-Controller. Retrieved May (2017). From http://edm.ares.com.tw/dm/newsletter-2014-11-BNK-AFEIS/it-1.php
[18] NetBean. Retrieved May (2017). From https://netbeans.org/
[19] Non-monotonic logic. Retrieved May (2017). From https://en.wikipedia.org/wiki/Non-monotonic_logic
[20] PrimesFaces. Retrieved May (2017). From http://www.primefaces.org/showcase/index.xhtml
[21] Sofie De Clercq, Steven Schockaert, Martine De Cock & Ann Nowe. (2016). Solving Stable Matching Problems using Answer Set Programming, Journal of Theory and Practice of Logic Programming, vol. 16, no. 3, pp. 247-268.
[22] Thomas Eiter, Giovambattista Ianni, & Thomas Krennwallner. (2009). Answer Set Programming: A Primer, Reasoning Web In Semantic Technologies for Information Systems (chap. 2, pp. 40-110).
[23] Kato, A. (1993). Complexity of the sex-equal stable marriage problem. Japan Journal of Industrial and Applied Mathematics, vol 10,no. 1,pp. 1–19.
[24] R. Irving, P. Leather, and D. Gusfield. (1987). An efficient algorithm for the “optimal” stable marriage. Journal of the ACM, vol. 34, no. 3, pp.532–543.
[25] D. Gus eld. (1987).Three fast algorithms for four problems in stable marriage. SIAM Journal of Comput, vol. 16, no.1, pp. 111-128.
[26] D. Gale and L. S. Shapley (1962).College Admissions and the Stability of Marriage. The American Mathematical Monthly, vol. 69, no. 1, pp. 9-15.
[27] V. Lifschitz(2002). Answer set programming and plan generation. Journal of Artificial Intelligence, vol.138,no. 1-2,pp. 39–54.
[28] 大學聯考分發. Retrieved May (2017). From http://ip194097.ntcu.edu.tw/Ungian/Chokphin/Hoagu/hunhoat/hunhoat.htm
[29] 黃詩婷 (2007)。台灣的大學入學制度經濟分析。國立中山大學經濟學研究所， 高雄市。
[30] 匈牙利演算法. Retrieved May (2017). From https://en.wikipedia.org/wiki/Hungarian_algorithm
[31]吳彥緯(2015)。實現熱門配對的演算法設計及複雜度分析。國立台灣大學資訊工程學系研究所，台北市。
描述 碩士
國立政治大學
資訊科學學系
103753030
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0103753030
資料類型 thesis
dc.contributor.advisor 陳正佳zh_TW
dc.contributor.advisor Chen, Cheng Chiaen_US
dc.contributor.author (Authors) 吳儼翰zh_TW
dc.contributor.author (Authors) Wu, Yan Hanen_US
dc.creator (作者) 吳儼翰zh_TW
dc.creator (作者) Wu, Yan Hanen_US
dc.date (日期) 2018en_US
dc.date.accessioned 1-Jun-2018 15:51:53 (UTC+8)-
dc.date.available 1-Jun-2018 15:51:53 (UTC+8)-
dc.date.issued (上傳時間) 1-Jun-2018 15:51:53 (UTC+8)-
dc.identifier (Other Identifiers) G0103753030en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/117428-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 103753030zh_TW
dc.description.abstract (摘要) 各式應用領域常會面臨許多撮合(Matching)問題，但當我們有需求時卻往往無法定出好的撮合策略，更遑論找到可實現此策略的電腦化解決方法。本研究希望針對穩定婚姻配對、大學聯考分發、論文審查分配、專題選修等等之類的撮合問題提供各種可行的通用撮合策略，可供使用者依其需求快速選用。而後續提供的支援系統則可據此產生一個以WEB為基礎的客製化專門應用領域撮合系統。
而什麼是撮合呢? 撮合是指有A、B兩群對象，在特定的規則與限制條件下，希望使每一A(B) 群對象可以連結至某些B(A)群對象，而使總體滿意度達到最大。以數學而言，一個A、B兩群間的撮合，就是一個滿足特定條件的A、B兩個集合間的二元關係。撮合類型可能是一對一、一對多、 多對多三種。一對一表示一個A群成員只能跟一個B群成員配對，一對多表示 一個A(B) 群成員能跟多個B(A) 群成員配對，多對多則指一個A群成員能跟多個B群成員配對且一個B群成員也能跟多個A群成員配對。
由於撮合型態與策略具有相當大的分歧性，以專用演算法實做並不實際，因此我們採用ASP(Answer set programming)實做撮合程式。ASP 是一種邏輯編程語言，具有宣告式程式特性，廣泛用於組合性問題的解決上，極適合應用在撮合策略的制定與實做。
在可真正執行撮合程式之前，必須預先建置A、B兩群對象的基本資料，因此我們的系統將允許開發者輸入A、B兩群對象的基本後設資料及撮合策略，而系統將據此建立對應Web介面與資料庫，允許使用者建立撮合對象的基本資料。一旦基本資料建立完成，系統即可依據系統設定的撮合策略以及以ASP實做的基本配對規則快速產生撮合結果，提供給使用者參考。		zh_TW
dc.description.abstract (摘要) There are a lot of application domains in which we may encounter the problem of finding a matching among two parties of entities. However, it is often the case that once a matching is needed, we cannot easily find a good matching strategy suitable for our purpose, not to mention one with a computerized implementation. This thesis aims to provide a web-based matching generation system allowing the quick generation of customized matching systems for users` need after their input of different demands of matching types and strategies. The supported types of matchings include most often used cases such as marriage/dating matching, paper review assignment, college admission dispatch and student-advisor selection etc.
What is a matching? A (bipartite) matching problem contains two parties of entities, each member of which has a preference over members of the opposite party. A matching in a matching problem is a binary relation between both parties of entities. The goal of a matching problem is to find one or more optimal matching in which the total satisfaction of both party members is maximized. Matching problems can be classified according restrictions imposed on matchings. 1-1 matching requires each member of both parties to be matched to at most one opposite party member, 1-m matching allows only members of one party to be matched to more than one opposite party member, and m-m matching allows members of both parties to be matched to more than one opposite party member.
Because there is a great variety of matching types and strategies, it is impractical to employ dedicated algorithm per case. It is thus eagerly expected to have a general framework in which different types of matching and strategies can be encoded. By applying Answer-set Programming (ASP) we provided one such framework in this thesis. ASP is logic programming language with declarative characteristics, widely applied in the solution of hard combinatorial problems, to be used in the encoding and solving of matching problems with different preference matching strategies.
Theoretical discussion of matching algorithms always assumes that party members and their preferences are available in advance. However, to engineer a matching system, we still need to provide means to achieve it. Our system is thus also a matching support system, through the web interface of which developers and end-users can enter meta and individual information about all concerned properties and/or preferences of party members. After a possibly further processing of users` preference on the values of concerned properties of opposite party members for deriving every member`s preference on the member of the opposite party, succeeding matching thus can obtain all needed data.		en_US
dc.description.tableofcontents 摘要 ii
Abstract iii
圖目錄 iv
表目錄 vi
第一章 序論 1
1.1 研究動機 1
1.2 實現方式 2
1.3論文貢獻與研究特色 2
1.4論文章節架構 3
第二章 相關研究 5
2.1 Java Server Faces 5
2.1.1 MVC框架 6
2.1.2 JSF 請求處理生命週期 7
2.1.3 Managed bean 8
2.2 Java Database Connectivity 8
2.3 Answer Set Programming 10
2.3.1 DLV和Clingo系統 12
2.4 Answer Set Programming求解方法: Generate and Test 16
2.5 穩定婚姻問題(Stable Marriage Problem) 18
2.6 撮合最佳化概念(Notions of Optimality of Model)相關文獻探討 21
第三章 運用ASP表達撮合問題 26
3.1穩定婚姻問題描述 26
3.2 專題選修問題描述 30
第四章 系統架構與實作 37
4.1 問題描述 37
4.2 系統運作架構 39
4.3系統JSF介面流程處理 40
4.3.1 系統GUI操作說明 42
4.3.2 Derby資料庫 54
4.3.3 Ajax 55
4.4 DLV後端撮合處理 57
第五章 範例結果展示 59
5.1 範例一:穩定婚姻配對問題 59
5.2 範例二:專題選修問題 62
5.3 範例三:大學聯考分發問題 63
5.4 範例四:論文審查匹配問題 66
第六章 結論與未來研究方向 69
6.1結論 69
6.2未來研究方向 70
參考文獻 72
附錄 75		zh_TW
dc.format.extent 1949132 bytes-
dc.format.mimetype application/pdf-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0103753030en_US
dc.subject (關鍵詞) 邏輯程式語言zh_TW
dc.subject (關鍵詞) 撮合配對zh_TW
dc.subject (關鍵詞) JSF2en_US
dc.subject (關鍵詞) Answer Set Programmingen_US
dc.title (題名) 快速生成建構於Web之客製化撮合系統zh_TW
dc.title (題名) Rapid Generation of Web-Based Customized Matching Systemsen_US
dc.type (資料類型) thesisen_US
dc.relation.reference (參考文獻) [1] Ajax. Retrieved May (2017). From https://zh.wikipedia.org/wiki/AJAX
[2] Alvin E. Roth, Tayfun Sonmez, & M. Utku Unver. (2004). Kidney Exchange, The Quarterly Journal of Economics, vol. 119, no. 2, pp. 457-488.
[3] Bipartite Matching. Retrieved May (2017). From http://www.csie.ntnu.edu.tw/~u91029/Matching.html#2
[4] Derby. Retrieved May (2017). From http://db.apache.org/derby/docs/10.6/ref/
[5] DLV - User Manual. Retrieved May (2017). From http://www.dlvsystem.com/html/DLV_User_Manual.html
[6] DLV Wrapper. Retrieved May (2017). From http://www.dlvsystem.com/dlvwrapper/#1
[7] Ed Burns, Chris, Schalk, & Neil Griffin. (2009). Java Server Faces 2.0 the Complete Reference.
[8] Faces Event. Retrieved May (2017). From http://openhome.cc/Gossip/JSF/ValueChangeEvents.htm
[9] FacesServlet. Retrieved May (2017). From https://docs.oracle.com/javaee/7/api/javax/faces/webapp/FacesServlet.html
[10] Gale-Shapley algorithm. Retrieved May (2017). From https://en.wikipedia.org/wiki/Stable_marriage_problem
[11] Irving, R.W. and Manlove, D.F. and O`Malley, G. (2009). Stable Marriage with Ties and Bounded Length Preference Lists. Journal of Discrete Algorithms, vol. 7, no. 2, pp. 213-219.
[12] Java Database Connectivity. Retrieved May (2017). From http://openhome.cc/Gossip/JavaGossip-V2/IntroduceJDBC.htm
[13] JSF Lifecycle. Retrieved May (2017). From http://www.w3ii.com/zh-TW/jsf/jsf_life_cycle.html
[14] Martin Gebser, Roland Kaminski, Benjamin Kaufmann, Marius Lindauer, Max Ostrowski, Javier Romero, Torsten Schaub, & Sven Thiele. (2017). Potassco User Guide 2.1.0 From https://github.com/potassco/guide/releases/
[15] Mario Alviano, Wolfgang Faber, Nicola Leone, Simona Perri, Gerald Pfeifer, & Giorgio Terracina. (2010). The Disjunctive Datalog System DLV, Proceedings of the First International Conference on Datalog Reloaded, pp. 282-301.
[16] Michael Gelfond, & Yulia Kahl. (2014).Knowledge Representation, Reasoning, and the Design of Intelligent Agents.
[17] Model-View-Controller. Retrieved May (2017). From http://edm.ares.com.tw/dm/newsletter-2014-11-BNK-AFEIS/it-1.php
[18] NetBean. Retrieved May (2017). From https://netbeans.org/
[19] Non-monotonic logic. Retrieved May (2017). From https://en.wikipedia.org/wiki/Non-monotonic_logic
[20] PrimesFaces. Retrieved May (2017). From http://www.primefaces.org/showcase/index.xhtml
[21] Sofie De Clercq, Steven Schockaert, Martine De Cock & Ann Nowe. (2016). Solving Stable Matching Problems using Answer Set Programming, Journal of Theory and Practice of Logic Programming, vol. 16, no. 3, pp. 247-268.
[22] Thomas Eiter, Giovambattista Ianni, & Thomas Krennwallner. (2009). Answer Set Programming: A Primer, Reasoning Web In Semantic Technologies for Information Systems (chap. 2, pp. 40-110).
[23] Kato, A. (1993). Complexity of the sex-equal stable marriage problem. Japan Journal of Industrial and Applied Mathematics, vol 10,no. 1,pp. 1–19.
[24] R. Irving, P. Leather, and D. Gusfield. (1987). An efficient algorithm for the “optimal” stable marriage. Journal of the ACM, vol. 34, no. 3, pp.532–543.
[25] D. Gus eld. (1987).Three fast algorithms for four problems in stable marriage. SIAM Journal of Comput, vol. 16, no.1, pp. 111-128.
[26] D. Gale and L. S. Shapley (1962).College Admissions and the Stability of Marriage. The American Mathematical Monthly, vol. 69, no. 1, pp. 9-15.
[27] V. Lifschitz(2002). Answer set programming and plan generation. Journal of Artificial Intelligence, vol.138,no. 1-2,pp. 39–54.
[28] 大學聯考分發. Retrieved May (2017). From http://ip194097.ntcu.edu.tw/Ungian/Chokphin/Hoagu/hunhoat/hunhoat.htm
[29] 黃詩婷 (2007)。台灣的大學入學制度經濟分析。國立中山大學經濟學研究所， 高雄市。
[30] 匈牙利演算法. Retrieved May (2017). From https://en.wikipedia.org/wiki/Hungarian_algorithm
[31]吳彥緯(2015)。實現熱門配對的演算法設計及複雜度分析。國立台灣大學資訊工程學系研究所，台北市。		zh_TW